On graphs containing a given graph as center
On graphs containing a given graph as center
复制标题
在包含给定图作为中心的图上
DOI：
10.1002/jgt.3190050413
复制
发表时间：
1981
期刊：
影响因子：
--
通讯作者：
P. Slater
中科院分区：
文献类型：
--
作者：
F. Buckley;Zevi Miller;P. Slater
我们研究将图 H 嵌入为超图 G 的中心的问题，并考虑可以限制 G 具有哪些属性。令 A(H) 表示具有与 H 中心同构的图 G 上的最小差异 ∣V(G)∣ - ∣V(H)∣，证明对于所有 H，A(H) ≤ 4，并且对于 0 ≤ i ≤ 4，我们用 A(T) = i 来表征树 T 的类。对于 n ≥ 2 和任何图 H，我们证明图 G 的点和边连通性等于 n，色数 X(G) = n + X(H)，其中心与 H 同构。最后，如果 ∣V(H)∣ ≥ 9 且 k ≥ ∣V(H)∣ + 1，则对于 n 足够大（当 k 为奇数时 n 为偶数），我们可以在 n 上构造 k-正则图中心与 H 同构的顶点。
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.