×

On 4-connected, planar 4-almost pancyclic graphs. (English) Zbl 0681.05047

A k-almost pancylic graph is one in which there are cycles of all lengths except k. In this paper, constructive methods are used to demonstrate the existence of 4-connected planar 4-almost pancyclic graphs on v vertices for \(v=30,36,39,42,44,45,46\) and all \(v\geq 48\). In addition, it is shown that these are the only values of v for which such graphs exist.
Reviewer: R.E.L.Aldred

MSC:

05C40 Connectivity
05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: EuDML

References:

[1] BARI R. A.: Regular Major Maps of at Most 19 Regions and their Q-Chromials. J. Comb. Theory Ser. B 12, 1972, 132-142. · Zbl 0211.56603 · doi:10.1016/0095-8956(72)90017-2
[2] BONDY J. A.: Pancyclic Graph. J. Comb. Theory Ser. B 11, 1971, 80-84. · Zbl 0183.52301 · doi:10.1016/0095-8956(71)90016-5
[3] CHOUDUM S. A.: Some 4-valent, 3-connected, planar, almost pancyclic graphs. Discrete Math. 18, 1977, 125-129. · Zbl 0357.05040 · doi:10.1016/0012-365X(77)90073-5
[4] MALKEVITCH J.: On the lengths of cycles in planar graphs. Recent Trends in Graph Theory (Proc. Conf., New York 1970), pp. 191 - 195. Lecture Notes in Mathematics, Vol. 186, Springer, Berlin 1971.
[5] ORE O.: The four color problem. Academia Press 1967. · Zbl 0149.21101
[6] TUTTE W. T.: A theorem on planar graphs. Trans. Amer. Math. Soc. 82, 1956, 99 - 116. · Zbl 0070.18403 · doi:10.2307/1992980
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.