Premium
The connected hub number and the connected domination number
Author(s) -
Johnson Peter,
Slater Peter,
Walsh Matt
Publication year - 2011
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20433
Subject(s) - combinatorics , vertex connectivity , induced subgraph , connectivity , connected component , mathematics , graph , induced path , path (computing) , strongly connected component , domination analysis , discrete mathematics , computer science , graph power , line graph , vertex (graph theory) , computer network
The connected hub number h c ( G ) of a connected graph G is the smallest order of a connected subgraph H of G such that any two nonadjacent vertices of G − H are joined in G by a path with all internal vertices in H . Letting γ c ( G ) denote the connected domination number of G , it is easy to see that h c ( G ) ≤ γ c ( G ) ≤ h c ( G ) + 1 for every connected graph G . Here we characterize the graphs G for which γ c ( G ) = h c ( G ) + 1. Our result contributes to the search for the solution of an extremal problem of (Newman‐Wolfe et al., Congressus Numerantium 67 (1988), 67–76). © 2011 Wiley Periodicals, Inc. NETWORKS, 2011
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom