Premium
On graphs containing a given graph as center
Author(s) -
Buckley Fred,
Miller Zevi,
Slater Peter J.
Publication year - 1981
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190050413
Subject(s) - combinatorics , mathematics , graph , center (category theory) , discrete mathematics , epigraph , mathematical optimization , chemistry , crystallography
We examine the problem of embedding a graph H as the center of a supergraph G , and we consider what properties one can restrict G to have. Letting A(H) denote the smallest difference ∣ V(G) ∣ ‐ ∣ V(H) ∣ over graphs G having center isomorphic to H it is demonstrated that A(H) ≤ 4 for all H , and for 0 ≤ i ≤ 4 we characterize the class of trees T with A(T) = i. for n ≥ 2 and any graph H , we demonstrate a graph G with point and edge connectivity equal to n , with chromatic number X(G) = n + X(H) , and whose center is isomorphic to H. Finally, if ∣ V(H) ∣ ≥ 9 and k ≥ ∣ V(H) ∣ + 1, then for n sufficiently large (with n even when k is odd) we can construct a k ‐regular graph on n vertices whose center is isomorphic to H .