极小循环图的圈点连通度
|
摘要
如果X-F中至少两个分支含圈,则称点集F为图X的一个圈点割.图X的所有圈点割的最小基数称为图x的圈点连通度,记为κ_c(X).在本文中,我们证明了极小循环图X=C(Z_n,S)在满足:(1)|S|≥2且对于a∈S有2a≡0(模n)或3α≡0(模n);或(2))|S|≥3且对任意的a∈S有2a■0(模n), 3a■0 (模n),则κ_c(X)=g(κ-2),其中g和κ(κ>2)分别为图X的围长和正则度.
A vertex cut F of a graph X is called a cyclic vertex cut if at least two components of X-F contain cycles. The cyclic vertex connectivity of X, denoted by κ_c(X),is the minimum cardinality of all cyclic vertex cuts. In this paper, we show that, for the minimal circulant graph X = C(Z_n,S),(1) if|S|≥ 2, and 2a≡0(mod n) or 3a≡ 0(mod n)for some a ∈ S, or (2) if |S| > 3, and 2a■0(mod n) and 3a■0(mod n) for any a∈ S, then κ_c(G) = g(k-2), where g and k(k > 2) are the girth and the regularity of X, respectively.
A vertex cut F of a graph X is called a cyclic vertex cut if at least two components of X-F contain cycles. The cyclic vertex connectivity of X, denoted by κ_c(X),is the minimum cardinality of all cyclic vertex cuts. In this paper, we show that, for the minimal circulant graph X = C(Z_n,S),(1) if|S|≥ 2, and 2a≡0(mod n) or 3a≡ 0(mod n)for some a ∈ S, or (2) if |S| > 3, and 2a■0(mod n) and 3a■0(mod n) for any a∈ S, then κ_c(G) = g(k-2), where g and k(k > 2) are the girth and the regularity of X, respectively.
引文
[1]Bondy J A, Murty U S R. Graph Theory, Graduate Texts in Mathematics 244. Berlin:SpringerVerlag, 2008
[2]Harary F. Conditional connectivity. Networks, 1983, 13:347-357
[3]Birkhoff G D. The reducibility of maps. Am. J. Math., 1913, 35:115-128
[4]Tait P G. Remaks on the coloring of maps. Proc. Roy. Soc., Edinburgh, 1880, 10:501-503
[5]Zhang C Q. Integer flows and cycle covers of graphs. Marcel Dekker Inc:New York, 1997
[6]Holton D A, Lou D, Plummer M D. On the 2-extendability of planner graphs. Discrete Math., 1991,96:81-99
[7]Lou D, Holton D A. Lower bound of cyclic edge connectivity for n-extendability of regular graphs.Discrete Math., 1993, 112:139-150
[8]Yu Z H, Liu Q H, Zhang Z. Cyclic vertex connectivity of star graphs. In:Proceedings of the 4th Annual International Conference on Combinatorial Optimization and Applications. LNCS, 2010,6508:212-221
[9]Cheng E,Lipták L,Qiu K, Shen Z. Cyclic vertex-connectivity of Cayley graphs generated by transposition trees. Graphs and Combinatorics, 2013, 29:835-841
[10]Boech F T, Tindell R. Circulants and their connectivity. J. Graph Theory, 1984, 8:487-499
[11]Feng R, Kwak J H. Circulant double coverings of a circulant graph of valency four. Graphs and Combinatorics, 2005, 21:386-400
[12]Feng R Q, Kwak J H. Circulant double coverings of a circulant graph of valency five. Acta Mathematica Sinica, English Series, 2007, 23(1):23-28
[13]Muga F P. Undirected circulant graphs. In:Int. Symp. Parallel Architectures, Algorithms and Networks, 1994, 113-118
[14]Stojmenovic I. Multiplicative circulant networks. Topological properties and communication algorithms. Discrete Appl. Math., 1997, 77:281-305
[15]Wasin S. Integral circulant graphs. Discrete Mathematics, 2005, 306:153-158
[16]Zhang F J, Huang Q X. Infinite circulants and their properties. Acta Mathematica Sinica, English Series, 1995, 11(3):280-284
[17]Mader W.über den Zusammen Symmetricher Graphen. Arch. Math., 1970, 21:331-336
[18]Tian Y Z, Meng J X. Restricted connectivity for some interconnection networks. Graphs and Combinatorics, 2015, 31(5):1727-1737
[2]Harary F. Conditional connectivity. Networks, 1983, 13:347-357
[3]Birkhoff G D. The reducibility of maps. Am. J. Math., 1913, 35:115-128
[4]Tait P G. Remaks on the coloring of maps. Proc. Roy. Soc., Edinburgh, 1880, 10:501-503
[5]Zhang C Q. Integer flows and cycle covers of graphs. Marcel Dekker Inc:New York, 1997
[6]Holton D A, Lou D, Plummer M D. On the 2-extendability of planner graphs. Discrete Math., 1991,96:81-99
[7]Lou D, Holton D A. Lower bound of cyclic edge connectivity for n-extendability of regular graphs.Discrete Math., 1993, 112:139-150
[8]Yu Z H, Liu Q H, Zhang Z. Cyclic vertex connectivity of star graphs. In:Proceedings of the 4th Annual International Conference on Combinatorial Optimization and Applications. LNCS, 2010,6508:212-221
[9]Cheng E,Lipták L,Qiu K, Shen Z. Cyclic vertex-connectivity of Cayley graphs generated by transposition trees. Graphs and Combinatorics, 2013, 29:835-841
[10]Boech F T, Tindell R. Circulants and their connectivity. J. Graph Theory, 1984, 8:487-499
[11]Feng R, Kwak J H. Circulant double coverings of a circulant graph of valency four. Graphs and Combinatorics, 2005, 21:386-400
[12]Feng R Q, Kwak J H. Circulant double coverings of a circulant graph of valency five. Acta Mathematica Sinica, English Series, 2007, 23(1):23-28
[13]Muga F P. Undirected circulant graphs. In:Int. Symp. Parallel Architectures, Algorithms and Networks, 1994, 113-118
[14]Stojmenovic I. Multiplicative circulant networks. Topological properties and communication algorithms. Discrete Appl. Math., 1997, 77:281-305
[15]Wasin S. Integral circulant graphs. Discrete Mathematics, 2005, 306:153-158
[16]Zhang F J, Huang Q X. Infinite circulants and their properties. Acta Mathematica Sinica, English Series, 1995, 11(3):280-284
[17]Mader W.über den Zusammen Symmetricher Graphen. Arch. Math., 1970, 21:331-336
[18]Tian Y Z, Meng J X. Restricted connectivity for some interconnection networks. Graphs and Combinatorics, 2015, 31(5):1727-1737