×

zbMATH — the first resource for mathematics

Circulants and their connectivities. (English) Zbl 0549.05048
Let \(C_ p<a_ 1,a_ 2,..,a_ k>\) be the circulant graph on p points such that the point numbered j is adjacent to \(j\pm a_ i\) (mod p) for \(i=1,2,...,k\). Here \(0<a_ 1<...<a_ k<{1\over2}(p+1)\). If \(\kappa\) is the point connectivity and \(\delta\) the degree of the graph, then the author’s main result is as follows: \(C_ p<a_ 1,a_ 2,...,a_ k>\) satisfies \(\kappa <\delta\) if and only if, for some proper divisor m of p, the number of distinct positive residues modulo m of the numbers \(a_ 1,a_ 2,...,a_ k\), \(p-a_ k\),...,\(p-a_ 1\) is less than the minimum of m-1 and \(\delta\) m/p. Some theorems regarding a generalization of connectivity called super-connectivity, are stated.
Reviewer: D.A.Holton

MSC:
05C99 Graph theory
05C40 Connectivity
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ádám, J. Combinatorial Theory 3 pp 393– (1967)
[2] Alspach, Congressus Numerantium 23 pp 131– (1979)
[3] Alspach, Discrete Math. 25 pp 97– (1979)
[4] Alspach, Ann. N. Y. Acad. Sci. 319 pp 18– (1979)
[5] Babai, Acta Math. Acad. Sci. Hungar. 29 pp 329– (1977)
[6] Babai, J. Combinatorial Theory B 27 pp 180– (1979)
[7] , , and , Connectivity extremal problems and the design of reliable probabilistic networks. The Theory and Applications of Graphs. Wiley, New York (1981) 45–54.
[8] Berggren, Bull. Austral. Math. Soc. 7 pp 131– (1962)
[9] Boesch, Networks 2 pp 261– (1972)
[10] Boesch, IEEE Trans. Circuit Theory 17 pp 183– (1971)
[11] and , Graph Theory with Applications. American Elsevier, New York (1976). · Zbl 1226.05083 · doi:10.1007/978-1-349-03521-2
[12] Chao, Trans. Amer. Math. Soc. 158 pp 247– (1971)
[13] Davidson, Theoret. Chim. Acta 58 pp 193– (1981)
[14] Circulant Matrices. Wiley, New York (1979).
[15] Elspas, J. Combinatorial Theory 9 pp 297– (1970)
[16] Harary, Proc. Natl. Acad. Sci. USA 48 pp 1142– (1962)
[17] Graph Theory. Addison-Wesley, Reading, MA (1969).
[18] Jackson, J. Graph Theory 2 pp 363– (1978)
[19] Mader, Arch. Math. (Basel) 21 pp 331– (1970) · Zbl 0201.56804 · doi:10.1007/BF01220924
[20] Mader, Arch. Math. (Basel) 22 pp 333– (1971) · doi:10.1007/BF01222585
[21] Mader, Math. Ann. 191 pp 21– (1971)
[22] Hamiltonian cycles in Cayley graphs. Submitted. · Zbl 0381.05038
[23] Marusic, Discrete Math. 42 pp 227– (1981)
[24] Marusic, Discrete Math. 43 pp 91– (1983)
[25] Tindell, Ann. Discrete Math. 13 pp 191– (1982)
[26] Edge connectivity properties of symmetric graphs. Submitted.
[27] Toida, J. Combinatorial Theory B 23 pp 239– (1977)
[28] Turner, J. Combinatorial Theory 3 pp 136– (1967)
[29] An investigation of the network reliability properties of circulant graphs. Doctoral dissertation, Stevens Institute of Technology (1983).
[30] Watkins, J. Combinatorial Theory 8 pp 23– (1970)
[31] Some classes of hypoconnected vertex-transitive graphs. Recent Progress in Combinatorics. Academic, New York (1969) 323–328.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.