Archive
Special Issues
A Two-Connected Graph with Gallai’s Property
Advances in Wireless Communications and Networks
Volume 5, Issue 1, June 2019, Pages: 29-32
Received: Jul. 11, 2019; Accepted: Aug. 14, 2019; Published: Sep. 17, 2019
Authors
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
Article Tools
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.
Keywords
Hypo-Hamiltonian, Hypo-Traceable, Hamiltonian, Gallai’s Property, Zamfirescu Criterion
Abdul Naeem Kalhoro, Ali Dino Jumani, A Two-Connected Graph with Gallai’s Property, Advances in Wireless Communications and Networks. Vol. 5, No. 1, 2019, pp. 29-32. doi: 10.11648/j.awcn.20190501.14
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.
PUBLICATION SERVICES