Heavy subgraph pairs for traceability of block-chains

Binlong Li; Hajo Broersma; Shenggui Zhang

Discussiones Mathematicae Graph Theory (2014)

  • Volume: 34, Issue: 2, page 287-307
  • ISSN: 2083-5892

Abstract

top
A graph is called traceable if it contains a Hamilton path, i.e., a path containing all its vertices. Let G be a graph on n vertices. We say that an induced subgraph of G is o−1-heavy if it contains two nonadjacent vertices which satisfy an Ore-type degree condition for traceability, i.e., with degree sum at least n−1 in G. A block-chain is a graph whose block graph is a path, i.e., it is either a P1, P2, or a 2-connected graph, or a graph with at least one cut vertex and exactly two end-blocks. Obviously, every traceable graph is a block-chain, but the reverse does not hold. In this paper we characterize all the pairs of connected o−1-heavy graphs that guarantee traceability of block-chains. Our main result is a common extension of earlier work on degree sum conditions, forbidden subgraph conditions and heavy subgraph conditions for traceability

How to cite

top

Binlong Li, Hajo Broersma, and Shenggui Zhang. "Heavy subgraph pairs for traceability of block-chains." Discussiones Mathematicae Graph Theory 34.2 (2014): 287-307. <http://eudml.org/doc/268015>.

@article{BinlongLi2014,
abstract = {A graph is called traceable if it contains a Hamilton path, i.e., a path containing all its vertices. Let G be a graph on n vertices. We say that an induced subgraph of G is o−1-heavy if it contains two nonadjacent vertices which satisfy an Ore-type degree condition for traceability, i.e., with degree sum at least n−1 in G. A block-chain is a graph whose block graph is a path, i.e., it is either a P1, P2, or a 2-connected graph, or a graph with at least one cut vertex and exactly two end-blocks. Obviously, every traceable graph is a block-chain, but the reverse does not hold. In this paper we characterize all the pairs of connected o−1-heavy graphs that guarantee traceability of block-chains. Our main result is a common extension of earlier work on degree sum conditions, forbidden subgraph conditions and heavy subgraph conditions for traceability},
author = {Binlong Li, Hajo Broersma, Shenggui Zhang},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {o−1-heavy subgraph; block-chain traceable graph; Ore-type condition; forbidden subgrap; -heavy subgraph; forbidden subgraph},
language = {eng},
number = {2},
pages = {287-307},
title = {Heavy subgraph pairs for traceability of block-chains},
url = {http://eudml.org/doc/268015},
volume = {34},
year = {2014},
}

TY - JOUR
AU - Binlong Li
AU - Hajo Broersma
AU - Shenggui Zhang
TI - Heavy subgraph pairs for traceability of block-chains
JO - Discussiones Mathematicae Graph Theory
PY - 2014
VL - 34
IS - 2
SP - 287
EP - 307
AB - A graph is called traceable if it contains a Hamilton path, i.e., a path containing all its vertices. Let G be a graph on n vertices. We say that an induced subgraph of G is o−1-heavy if it contains two nonadjacent vertices which satisfy an Ore-type degree condition for traceability, i.e., with degree sum at least n−1 in G. A block-chain is a graph whose block graph is a path, i.e., it is either a P1, P2, or a 2-connected graph, or a graph with at least one cut vertex and exactly two end-blocks. Obviously, every traceable graph is a block-chain, but the reverse does not hold. In this paper we characterize all the pairs of connected o−1-heavy graphs that guarantee traceability of block-chains. Our main result is a common extension of earlier work on degree sum conditions, forbidden subgraph conditions and heavy subgraph conditions for traceability
LA - eng
KW - o−1-heavy subgraph; block-chain traceable graph; Ore-type condition; forbidden subgrap; -heavy subgraph; forbidden subgraph
UR - http://eudml.org/doc/268015
ER -

References

top
  1. [1] P. Bedrossian, G. Chen, and R.H. Schelp, A generalization of Fan’s condition for hamiltonicity, pancyclicity, and hamiltonian connectedness, Discrete Math. 115 (1993) 39-50. doi:10.1016/0012-365X(93)90476-A[Crossref] Zbl0773.05075
  2. [2] J.A. Bondy and U.S.R. Murty, Graph Theory, Springer Graduate Texts in Mathe- matics 244 (2008). 
  3. [3] H.J. Broersma, Z. Ryj´aˇcek and I. Schiermeyer, Dirac’s minimum degree condition restricted to claws, Discrete Math. 167/168 (1997) 155-166. doi:10.1016/S0012-365X(96)00224-5[Crossref] 
  4. [4] H.J. Broersma and H.J. Veldman, Restrictions on induced subgraphs ensuring hamil- tonicity or pancyclicity of K1,3-free graphs, in: R. Bodendiek (Ed.) Contemporary Methods in Graph Theory, (BI Wissenschaftsverlag, Mannheim-Wien-Zfirich, 1990) 181-194. 
  5. [5] R. Čada, Degree conditions on induced claws, Discrete Math. 308 (2008) 5622-5631. doi:10.1016/j.disc.2007.10.026[Crossref][WoS] Zbl1175.05069
  6. [6] D. Duffus, R.J. Gould and M.S. Jacobson, Forbidden subgraphs and the hamiltonian theme, in: The Theory and Applications of Graphs (Kalamazoo, Mich. 1980, Wiley, New York, 1981) 297-316. 
  7. [7] R.J. Faudree and R.J. Gould, Characterizing forbidden pairs for Hamiltonian prop- erties, Discrete Math. 173 (1997) 45-60. doi:10.1016/S0012-365X(96)00147-1[Crossref] 
  8. [8] 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
  9. [9] B. Li, H.J. Broersma and S. Zhang, Forbidden subgraph pairs for traceability of block-chains, Electron. J. Graph Theory Appl. 1 (2013) 1-10. Zbl1306.05205
  10. [10] B. Li, Z. Ryjáček, Y.Wang and S. Zhang, Pairs of heavy subgraphs for Hamiltonicity of 2-connected graphs, SIAM J. Discrete Math. 26 (2012) 1088-1103. doi:10.1137/11084786X[WoS] Zbl1256.05052
  11. [11] B. Li and S. Zhang, On traceability of claw-o−1-heavy graphs (2013). arXiv:1303.0991v1 

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.