Pancyclicity and Panconnectedness of Line Graphs of Graphs at Most One Cycle

Authors

  • Sirirat Singhun Faculty of Science, Ramkhamhaeng University
  • Adthasit Sinna
  • Chapkit Charnsamorn
  • Pensiri Sompong

Keywords:

pancyclic; panconnected; Hamiltonian cycle; line graph

Abstract

Let G be a simple graph. The line graph of G, denoted by L(G), is the graph obtained by taking the edges of G as vertices and joining two of these vertices whenever the corresponding edges in G have a vertex in common. A graph is called pancyclic if it contains cycles of length three up to its Hamiltonian cycle and it is called panconnected if, between any pair of distinct vertices u and v, it contains paths of length d(u, v) up to its Hamiltonian path. In this paper, we consider a tree and a unicyclic graph, and give necessary and sufficient conditions for their line graphs to be pancyclic and panconnected, respectively.

References

F. Harary and C.St.J.A. Nash-Williams, Oneulerian and Hamiltonian graphs and line graphs, Can. Math. Bull. (1965) 701–710.

Chia GL, Hemakul W and Singhun S (2017) Graphs with cyclomatic number three having panconnected square. Discrete mathematics, Algorithm and applications 14 page DOI:10.1142/S1793830917500677

Harary F and Nash-Williams C St JA (1965) On eulerian and Hamiltonian graphs and line graphs, Can. Math. Bull. 701–710.

v1n1

Downloads

Published

2021-04-30

Issue

Vol. 3 No. 1 (2020): January - April

Section

Original Articles

License

Copyright Notice: a copyright on any article in the  published journal is retained by the Ramkhamhaeng International Journal of Science and Technology. Readers or Users grant the right to use of the Article contained in the Content in accordance with the Creative Commons CC BY-NC-ND license and the Data contained in the Content in accordance with the Creative Commons CC BY-NC-ND.