Geodesic
Heavy subgraph pairs for traceability of block-chains
Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 2, pp. 287-307

Voir la notice de l'article provenant de la source Library of Science

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 P_1, P_2, 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
Keywords: block-chain traceable graph, Ore-type condition, forbidden subgrap, $o_{−1}$-heavy subgraph 
@article{DMGT_2014_34_2_a6,
     author = {Li, Binlong and Broersma, Hajo and Zhang, Shenggui},
     title = {Heavy subgraph pairs for traceability of block-chains},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {287--307},
     publisher = {mathdoc},
     volume = {34},
     number = {2},
     year = {2014},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2014_34_2_a6/}
}
TY  - JOUR
AU  - Li, Binlong
AU  - Broersma, Hajo
AU  - Zhang, Shenggui
TI  - Heavy subgraph pairs for traceability of block-chains
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2014
SP  - 287
EP  - 307
VL  - 34
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2014_34_2_a6/
LA  - en
ID  - DMGT_2014_34_2_a6
ER  - 
%0 Journal Article
%A Li, Binlong
%A Broersma, Hajo
%A Zhang, Shenggui
%T Heavy subgraph pairs for traceability of block-chains
%J Discussiones Mathematicae. Graph Theory
%D 2014
%P 287-307
%V 34
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2014_34_2_a6/
%G en
%F DMGT_2014_34_2_a6
Li, Binlong; Broersma, Hajo; Zhang, Shenggui. Heavy subgraph pairs for traceability of block-chains. Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 2, pp. 287-307. http://geodesic.mathdoc.fr/item/DMGT_2014_34_2_a6/