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