- Tytuł:
- Heavy subgraph pairs for traceability of block-chains
- Autorzy:
-
Li, Binlong
Broersma, Hajo
Zhang, Shenggui - Powiązania:
- https://bibliotekanauki.pl/articles/30148234.pdf
- Data publikacji:
- 2014-05-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
block-chain traceable graph
Ore-type condition
forbidden subgrap
$o_{−1}$-heavy subgraph - Opis:
- 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
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2014, 34, 2; 287-307
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł