| Peer-Reviewed

A Two-Connected Graph with Gallai’s Property

Received: 11 July 2019     Accepted: 14 August 2019     Published: 17 September 2019
Views:       Downloads:
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
  • 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
  • Department of Mathematics, Faculty of Physical Sciences, Shah Abdul Latif University, Khairpur, Pakistan

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

  • Sections