On k-Path Pancyclic Graphs

Zhenming Bi; Ping Zhang

Discussiones Mathematicae Graph Theory (2015)

  • Volume: 35, Issue: 2, page 271-281
  • ISSN: 2083-5892

Abstract

top
For integers k and n with 2 ≤ k ≤ n − 1, a graph G of order n is k-path pancyclic if every path P of order k in G lies on a cycle of every length from k + 1 to n. Thus a 2-path pancyclic graph is edge-pancyclic. In this paper, we present sufficient conditions for graphs to be k-path pancyclic. For a graph G of order n ≥ 3, we establish sharp lower bounds in terms of n and k for (a) the minimum degree of G, (b) the minimum degree-sum of nonadjacent vertices of G and (c) the size of G such that G is k-path pancyclic

How to cite

top

Zhenming Bi, and Ping Zhang. "On k-Path Pancyclic Graphs." Discussiones Mathematicae Graph Theory 35.2 (2015): 271-281. <http://eudml.org/doc/271089>.

@article{ZhenmingBi2015,
abstract = {For integers k and n with 2 ≤ k ≤ n − 1, a graph G of order n is k-path pancyclic if every path P of order k in G lies on a cycle of every length from k + 1 to n. Thus a 2-path pancyclic graph is edge-pancyclic. In this paper, we present sufficient conditions for graphs to be k-path pancyclic. For a graph G of order n ≥ 3, we establish sharp lower bounds in terms of n and k for (a) the minimum degree of G, (b) the minimum degree-sum of nonadjacent vertices of G and (c) the size of G such that G is k-path pancyclic},
author = {Zhenming Bi, Ping Zhang},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {Hamiltonian; panconnected; pancyclic; path Hamiltonian; path pancyclic; Hamiltonian graph; panconnected graph; pancyclic graph; path-Hamiltonian graph; path-pancyclic graph},
language = {eng},
number = {2},
pages = {271-281},
title = {On k-Path Pancyclic Graphs},
url = {http://eudml.org/doc/271089},
volume = {35},
year = {2015},
}

TY - JOUR
AU - Zhenming Bi
AU - Ping Zhang
TI - On k-Path Pancyclic Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2015
VL - 35
IS - 2
SP - 271
EP - 281
AB - For integers k and n with 2 ≤ k ≤ n − 1, a graph G of order n is k-path pancyclic if every path P of order k in G lies on a cycle of every length from k + 1 to n. Thus a 2-path pancyclic graph is edge-pancyclic. In this paper, we present sufficient conditions for graphs to be k-path pancyclic. For a graph G of order n ≥ 3, we establish sharp lower bounds in terms of n and k for (a) the minimum degree of G, (b) the minimum degree-sum of nonadjacent vertices of G and (c) the size of G such that G is k-path pancyclic
LA - eng
KW - Hamiltonian; panconnected; pancyclic; path Hamiltonian; path pancyclic; Hamiltonian graph; panconnected graph; pancyclic graph; path-Hamiltonian graph; path-pancyclic graph
UR - http://eudml.org/doc/271089
ER -

References

top
  1. [1] Y. Alavi and J.E. Williamson, Panconnected graphs, Studia Sci. Math. Hungar. 10 (1975) 19-22. Zbl0354.05038
  2. [2] H.C. Chan, J.M. Chang, Y.L. Wang and S.J. Horng, Geodesic-pancyclic graphs, Discrete Appl. Math. 155 (2007) 1971-1978. Zbl1124.05051
  3. [3] G. Chartrand, F. Fujie and P. Zhang, On an extension of an observation of Hamilton, J. Combin. Math. Combin. Comput., to appear. 
  4. [4] G. Chartrand, A.M. Hobbs, H.A. Jung, S.F. Kapoor and C.St.J.A. Nash-Williams, The square of a block is Hamiltonian connected, J. Combin. Theory (B) 16 (1974) 290-292. doi:10.1016/0095-8956(74)90075-6[Crossref] 
  5. [5] G. Chartrand and S.F. Kapoor, The cube of every connected graph is 1-hamiltonian, J. Res. Nat. Bur. Standards B 73 (1969) 47-48. doi:10.6028/jres.073B.007 Zbl0174.26802
  6. [6] G. Chartrand, L. Lesniak and P. Zhang, Graphs & Digraphs: 5th Edition (Chapman & Hall/CRC, Boca Raton, FL, 2010). 
  7. [7] G.A. Dirac, Some theorems on abstract graphs, Proc. London Math. Soc. 2 (1952) 69-81. doi:10.1112/plms/s3-2.1.69[Crossref] 
  8. [8] R.J. Faudree and R.H. Schelp, Path connected graphs, Acta Math. Acad. Sci. Hun- gar. 25 (1974) 313-319. doi:10.1007/BF01886090[Crossref] Zbl0294.05119
  9. [9] H. Fleischner, The square of every two-connected graph is Hamiltonian, J. Combin. Theory (B) 16 (1974) 29-34. doi:10.1016/0095-8956(74)90091-4[Crossref] Zbl0256.05121
  10. [10] C.St.J.A. Nash-Williams, Problem No. 48, in: Theory of Graphs and its Applica- tions, (Academic Press, New York 1968), 367. 
  11. [11] O. Ore, Note on Hamilton circuits, Amer. Math. Monthly 67 (1960) 55. doi:10.2307/2308928[Crossref] Zbl0089.39505
  12. [12] O. Ore, Hamilton connected graphs, J. Math. Pures Appl. 42 (1963) 21-27. Zbl0106.37103
  13. [13] B. Randerath, I. Schiermeyer, M. Tewes and L. Volkmann, Vertex pancyclic graphs, Discrete Appl. Math. 120 (2002) 219-237. doi:10.1016/S0166-218X(01)00292-X[Crossref] Zbl1001.05070
  14. [14] M. Sekanina, On an ordering of the set of vertices of a connected graph, Publ. Fac. Sci. Univ. Brno 412 (1960) 137-142. 
  15. [15] J.E. Williamson, Panconnected graphs II , Period. Math. Hungar. 8 (1977) 105-116. doi:10.1007/BF02018497 [Crossref] Zbl0339.05110

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.