A Two-Connected Graph with Gallai’s Property

Abdul Naeem Kalhoro; Ali Dino Jumani

doi:doi:10.11648/j.awcn.20190501.14

| Peer-Reviewed

A Two-Connected Graph with Gallai’s Property

Abdul Naeem Kalhoro, Ali Dino Jumani

Published in Advances in Wireless Communications and Networks (Volume 5, Issue 1)

Received: 11 July 2019 Accepted: 14 August 2019 Published: 17 September 2019

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

Abstract

The most famous examples of Hypo-Hamiltonian graph is the Petersen graph. Before the discovery of Hypo-traceable graphs, Tibor Gallai, in 1966, raised the question whether the graphs in which each vertex is missed by some longest path. This property will be called Gallai’s property, various authors worked on that property. In 1969, Gallai’s question was first replied through H. Walther, who introduced a planar graph on 25 vertices satisfying Gallai’s criterion. Furthermore, H. Walther and H. Voss and Tudor Zamfirescu introduced the graph with 12 vertices and it was guessed that order 12 is the smaller possibility of such a graphLater the question was modifies by Tudor Zamfirescu and asked that whether there exists graphs of Paths and Cycles, that is to say i-connected graphs (planar or non-planar respectively), such that each set of j points are disjoint from some longest paths or cycles., Several good examples answering Tudor Zamfirescu’s questions were published. In this note a graphs is developed with the property that everyone vertex is missed by some longest cycle with connectivity 2, satisfying Gallai’s property. The designed graphs can be useful in various fields of science and technology including computational geometry, networking, theoretical computer science and circuit designing.

Published in	Advances in Wireless Communications and Networks (Volume 5, Issue 1)
DOI	10.11648/j.awcn.20190501.14
Page(s)	29-32
Creative Commons	This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.
Copyright	Copyright © The Author(s), 2019. Published by Science Publishing Group

Keywords

Hypo-Hamiltonian, Hypo-Traceable, Hamiltonian, Gallai’s Property, Zamfirescu Criterion

References

[1]	P. Erdos and G. Katona (eds.), Theory of Graphs, Proc. Colloq. Tihany, Hungary, Sept. 1966, Academic Press, New York (1968).
[2]	H. Walther, Uber die Nichtexistenz eines Knotenpunktes, durch den alle langsten Wege eines Graphen gehen, J. Comb. Theory 6 (1969) 1-6.
[3]	H. Walther, H. J. Voss, Uber Kreise in Graphen, VEB Deutscher Verlag der Wissenschaften, Berlin, 1974.
[4]	T. Zamfirescu, A two-Connected Planar Graph without Concurrent Longest Paths, J. Combin. Theory B13 (1972) 116-121.
[5]	W. Schmitz, Uber Langste Wege und Kreise in Graphen, Rend. Sem. Mat. Univ. Padova 53 (1975) 97-103.
[6]	T. Zmfirescu, on longest paths and circuits in graphs, Math. Scand. 38 (1976) 211-239.
[7]	T. Zamfirescue, intersecting longest paths or cycles: A short survey, Analele Univ. Craiova, Seria Mat. Info. 28 (2001) 1-9.
[8]	H. WALTHER, Uber die Nichtexistenz zweier Knotenpunkte eines Graphen, die alle llngsten Kreise fassen, J. Combinatorial Theory 8 (1970), 330-333.
[9]	B. Grunbaum, Vertices missed by longest paths or circuits, J. Comb. Theory, A 17 (1974), 31-38.
[10]	W. Hatzel, Ein planarer hypohamiltonscher Graph mit 57 Knoten, Math. Ann. 243 (1979), 213-216.
[11]	T. Zamfirescu, Graphen, in welchen je zwei Eckpunkte durch einen langsten Weg vermieden werden, Rend. Sem. Mat. Univ. Ferrara 21 (1975), 17–24.
[12]	T. Zamfirescu, L'histoire et l'´etat pr´esent des bornes connues pour Pkj, Ckj, Pkj et Ckj, Cahiers CERO 17 (1975), 427-439.
[13]	Abdul Naeem & Ali Dino Jumani, ”Graph with non-concurrent Longest Paths”. IJCSIS International Journal of Computer Science and Information Security, VOL. 17 No. 4, April 2019.
[14]	Abdul Naeem & Ali Dino Jumani. “A Planar Lattice Graph, with Empty Intersection of All Longest Path”. Engineering Mathematics. Vol. 3, No. 1, 2019, pp. 6-8. doi:10.11648/j.engmath.20190301.12.
[15]	A. H JUNEJO, I AHMED, I. SOOMRO, A. N KALHORO, R MUHAMMAD, I ALI JOKHIO, R CHOHAN, A. D JUMANI. “A Connected Graph with set of empty Intersection of All Longest Cycles”. IJCSNS International Journal of Computer Science and Network Security, VOL. 19 No. 5, May 2019.
[16]	A. H Junejo, A. N Kalhoro, Inayatullah soomro, Israr Ahmed, Raza Muhammad, Imdad Ali Jokhio, Rozina Chohan. “A Connected Graph with Non-concurrent Longest Cycles”. IJCSNS International Journal of Computer Science and Network Security, VOL. 19 No. 5, May 2019.
[17]	A. H JUNEJO, A. N KALHORO, I AHMED, I SOOMRO, R MUHAMMAD, I ALI JOKHIO, R CHOHAN, A. D JUMANI, “A connected graph with non-concurrent Longest Paths”, IJCSNS International Journal of Computer Science and Network Security, VOL. 19 No. 4, April 2019.

Cite This Article

Plain Text BibTeX RIS

APA Style

Abdul Naeem Kalhoro, Ali Dino Jumani. (2019). A Two-Connected Graph with Gallai’s Property. Advances in Wireless Communications and Networks, 5(1), 29-32. https://doi.org/10.11648/j.awcn.20190501.14

Copy | Download

ACS Style

Abdul Naeem Kalhoro; Ali Dino Jumani. A Two-Connected Graph with Gallai’s Property. Adv. Wirel. Commun. Netw. 2019, 5(1), 29-32. doi: 10.11648/j.awcn.20190501.14

Copy | Download

AMA Style

Abdul Naeem Kalhoro, Ali Dino Jumani. A Two-Connected Graph with Gallai’s Property. Adv Wirel Commun Netw. 2019;5(1):29-32. doi: 10.11648/j.awcn.20190501.14

Copy | Download

@article{10.11648/j.awcn.20190501.14,
  author = {Abdul Naeem Kalhoro and Ali Dino Jumani},
  title = {A Two-Connected Graph with Gallai’s Property},
  journal = {Advances in Wireless Communications and Networks},
  volume = {5},
  number = {1},
  pages = {29-32},
  doi = {10.11648/j.awcn.20190501.14},
  url = {https://doi.org/10.11648/j.awcn.20190501.14},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.awcn.20190501.14},
  abstract = {The most famous examples of Hypo-Hamiltonian graph is the Petersen graph. Before the discovery of Hypo-traceable graphs, Tibor Gallai, in 1966, raised the question whether the graphs in which each vertex is missed by some longest path. This property will be called Gallai’s property, various authors worked on that property. In 1969, Gallai’s question was first replied through H. Walther, who introduced a planar graph on 25 vertices satisfying Gallai’s criterion. Furthermore, H. Walther and H. Voss and Tudor Zamfirescu introduced the graph with 12 vertices and it was guessed that order 12 is the smaller possibility of such a graphLater the question was modifies by Tudor Zamfirescu and asked that whether there exists graphs of Paths and Cycles, that is to say i-connected graphs (planar or non-planar respectively), such that each set of j points are disjoint from some longest paths or cycles., Several good examples answering Tudor Zamfirescu’s questions were published. In this note a graphs is developed with the property that everyone vertex is missed by some longest cycle with connectivity 2, satisfying Gallai’s property.  The designed graphs can be useful in various fields of science and technology including computational geometry, networking, theoretical computer science and circuit designing.},
 year = {2019}
}

Copy | Download

TY - JOUR
T1 - A Two-Connected Graph with Gallai’s Property
AU - Abdul Naeem Kalhoro
AU - Ali Dino Jumani
Y1 - 2019/09/17
PY - 2019
N1 - https://doi.org/10.11648/j.awcn.20190501.14
DO - 10.11648/j.awcn.20190501.14
T2 - Advances in Wireless Communications and Networks
JF - Advances in Wireless Communications and Networks
JO - Advances in Wireless Communications and Networks
SP - 29
EP - 32
PB - Science Publishing Group
SN - 2575-596X
UR - https://doi.org/10.11648/j.awcn.20190501.14
AB - The most famous examples of Hypo-Hamiltonian graph is the Petersen graph. Before the discovery of Hypo-traceable graphs, Tibor Gallai, in 1966, raised the question whether the graphs in which each vertex is missed by some longest path. This property will be called Gallai’s property, various authors worked on that property. In 1969, Gallai’s question was first replied through H. Walther, who introduced a planar graph on 25 vertices satisfying Gallai’s criterion. Furthermore, H. Walther and H. Voss and Tudor Zamfirescu introduced the graph with 12 vertices and it was guessed that order 12 is the smaller possibility of such a graphLater the question was modifies by Tudor Zamfirescu and asked that whether there exists graphs of Paths and Cycles, that is to say i-connected graphs (planar or non-planar respectively), such that each set of j points are disjoint from some longest paths or cycles., Several good examples answering Tudor Zamfirescu’s questions were published. In this note a graphs is developed with the property that everyone vertex is missed by some longest cycle with connectivity 2, satisfying Gallai’s property. The designed graphs can be useful in various fields of science and technology including computational geometry, networking, theoretical computer science and circuit designing.
VL - 5
IS - 1
ER -

Copy | Download

Author Information

Abdul Naeem Kalhoro

Department of Mathematics, Faculty of Physical Sciences, Shah Abdul Latif University, Khairpur, Pakistan
Ali Dino Jumani

Department of Mathematics, Faculty of Physical Sciences, Shah Abdul Latif University, Khairpur, Pakistan

Download PDF

Sections

Plain Text BibTeX RIS

APA Style

Abdul Naeem Kalhoro, Ali Dino Jumani. (2019). A Two-Connected Graph with Gallai’s Property. Advances in Wireless Communications and Networks, 5(1), 29-32. https://doi.org/10.11648/j.awcn.20190501.14

Copy | Download

ACS Style

Abdul Naeem Kalhoro; Ali Dino Jumani. A Two-Connected Graph with Gallai’s Property. Adv. Wirel. Commun. Netw. 2019, 5(1), 29-32. doi: 10.11648/j.awcn.20190501.14

Copy | Download

AMA Style

Abdul Naeem Kalhoro, Ali Dino Jumani. A Two-Connected Graph with Gallai’s Property. Adv Wirel Commun Netw. 2019;5(1):29-32. doi: 10.11648/j.awcn.20190501.14

Copy | Download

@article{10.11648/j.awcn.20190501.14,
  author = {Abdul Naeem Kalhoro and Ali Dino Jumani},
  title = {A Two-Connected Graph with Gallai’s Property},
  journal = {Advances in Wireless Communications and Networks},
  volume = {5},
  number = {1},
  pages = {29-32},
  doi = {10.11648/j.awcn.20190501.14},
  url = {https://doi.org/10.11648/j.awcn.20190501.14},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.awcn.20190501.14},
  abstract = {The most famous examples of Hypo-Hamiltonian graph is the Petersen graph. Before the discovery of Hypo-traceable graphs, Tibor Gallai, in 1966, raised the question whether the graphs in which each vertex is missed by some longest path. This property will be called Gallai’s property, various authors worked on that property. In 1969, Gallai’s question was first replied through H. Walther, who introduced a planar graph on 25 vertices satisfying Gallai’s criterion. Furthermore, H. Walther and H. Voss and Tudor Zamfirescu introduced the graph with 12 vertices and it was guessed that order 12 is the smaller possibility of such a graphLater the question was modifies by Tudor Zamfirescu and asked that whether there exists graphs of Paths and Cycles, that is to say i-connected graphs (planar or non-planar respectively), such that each set of j points are disjoint from some longest paths or cycles., Several good examples answering Tudor Zamfirescu’s questions were published. In this note a graphs is developed with the property that everyone vertex is missed by some longest cycle with connectivity 2, satisfying Gallai’s property.  The designed graphs can be useful in various fields of science and technology including computational geometry, networking, theoretical computer science and circuit designing.},
 year = {2019}
}

Copy | Download