Archimedean tiling graphs with Gallai’s property

Zhikui Chang; Liping Yuan

doi:10.1515/auom-2017-0029

.blurhash-client-img { display: none !important; }

Archimedean tiling graphs with Gallai’s property

Analele ştiinţifice ale Universităţii "Ovidius" Constanţa. Seria Matematică

Volume 25 (2017): Issue 2 (July 2017)

By: Zhikui Chang and Liping Yuan

Open Access

|Sep 2017

Abstract

Gallai in 1966 raised the question about the existence of graphs with the property that every vertex is missed by some longest path. This property will be called Gallai’s property. In this paper we present some graphs embeddable into Archimedean tiling graphs, with both connectivity 1 and 2, satisfying Gallai’s property.

References

[1] Y. Bashir, T. Zamfirescu, Lattice graphs with Gallai's property, Bull. Math. Soc. Sci. Math. Roumanie 56 (2013) 65-71.
Search in Google Scholar Back to article
[2] T. Gallai, Problem 4, in: Theory of Graphs, Proc. Tihany 1966 (ed: P. Erdős and G. Katona), Academic Press, New York, 1968, 362.
Search in Google Scholar Back to article
[3] V. S. Gordon, Y. L. Orlovich and F. Werner, Hamiltonian properties of triangular grid graphs, Discrete Math. 308 (2008) 6166-6188.10.1016/j.disc.2007.11.040
Search in Google Scholar Back to article
[4] B. Grünbaum, Vertices missed by longest paths or circuits, J. Comb. Theory A 17 (1974) 31-38.10.1016/0097-3165(74)90025-9
Open DOI Search in Google Scholar Back to article
[5] Grünbaum, B., Shephard, G. C., Tilings and Patterns. New York: W. H. Freeman and Company, 1987.
Search in Google Scholar Back to article
[6] A. D. Jumani and T. Zamfirescu, On longest paths in triangular lattice graphs, Util. Math. 89 (2012) 269-273.
Search in Google Scholar Back to article
[7] S. Klavžar, M. Petkov_sek, Graphs with non empty intersection of longest paths, Ars Combin. 29 (1990) 13-52.
Search in Google Scholar Back to article
[8] B. Menke, Ch. Zamfirescu and T. Zamfirescu, Intersections of longest cycles in grid graphs, J. Graph Theory 25 (1997) 37-52.10.1002/(SICI)1097-0118(199705)25:1<;37::AID-JGT2>3.0.CO;2-J
Search in Google Scholar Back to article
[9] F. Nadeem, A. Shabbir, and T. Zamfirescu, Planar lattice graphs with Gallais property, Graphs Combin. 29 (2013) 1523-1529.10.1007/s00373-012-1177-8
Open DOI Search in Google Scholar Back to article
[10] W. Schmitz, über längste Wege und Kreise in Graphen, Rend. Sem. Mat. Univ. Padova 53 (1975) 97-103.
Search in Google Scholar Back to article
[11] Z. Skupień, Smallest sets of longest paths with empty intersection, Combin. Probab. Comput. 5 (1996), 429C436.10.1017/S0963548300002170
Search in Google Scholar Back to article
[12] W. T. Tutte, A theorem on planar graphs, Trans. Amer. Soc. 82 (1956) 99-116.10.1090/S0002-9947-1956-0081471-8
Open DOI Search in Google Scholar Back to article
[13] H. Walther, über die Nichtexistenz eines Knotenpunktes, durch den alle längsten Wege eines Graphen gehen, J. Comb. Theory 6 (1969) 1-6.10.1016/S0021-9800(69)80098-0
Search in Google Scholar Back to article
[14] H. Walther and H.-J. Voss, über Kreise in Graphen, VEB Deutscher Verlag der Wissenschaften, Berlin, 1974.
Search in Google Scholar Back to article
[15] T. Zamfirescu, A two-connected planar graph without concurrent longest paths, J. Combin. Theory B 13 (1972) 116-121.10.1016/0095-8956(72)90048-2
Search in Google Scholar Back to article
[16] T. Zamfirescu, On longest paths and circuits in graphs, Math. Scand. 38 (1976) 211-239.10.7146/math.scand.a-11630
Open DOI Search in Google Scholar Back to article
[17] T. Zamfirescu, Intersecting longest paths or cycles: a short survey, Analele Univ. Craiova, Ser. Mat. Inf. 28 (2001) 1-9.
Search in Google Scholar Back to article

Articles in this issue

DOI: https://doi.org/10.1515/auom-2017-0029 | Journal eISSN: 1844-0835 | Journal ISSN: 1224-1784

Journal RSS Feed

Language: English

Page range: 185 - 199

Submitted on: Apr 1, 2016

Accepted on: Apr 1, 2016

Published on: Sep 21, 2017

Published by: Ovidius University of Constanta

In partnership with: Paradigm Publishing Services

Publication frequency: 3 issues per year

Keywords:

Gallai’s property,

Archimedean tiling graphs,

the longest path

Related subjects:

Mathematics,

General mathematics

© 2017 Zhikui Chang, Liping Yuan, published by Ovidius University of Constanta
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Volume 25 (2017): Issue 2 (July 2017)