Nontraceable detour graphs (Q868352): Difference between revisions
From MaRDI portal
Removed claim: author (P16): Item:Q593274 |
Changed an Item |
||
Property / author | |||
Property / author: Gabriel Semanisin / rank | |||
Normal rank |
Revision as of 20:40, 19 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Nontraceable detour graphs |
scientific article |
Statements
Nontraceable detour graphs (English)
0 references
2 March 2007
0 references
Let \(G\) be a graph with vertex set \(V(G)\). The detour order of a vertex \(v\in V(G)\) is the order of a longest path in \(G\) with initial vertex \(v\), and the detour order of \(G\) is the maximum of the detour orders of its vertices. The detour sequence of \(G\) is a sequence consisting of the detour orders of its vertices. A graph is called a detour graph if its detour sequence is constant. The detour deficiency of a graph \(G\) is the difference between \(| V(G)| \) and its detour order. A graph \(G\) is traceable if its detour order is equal \(| V(G)| \). The authors present a number of constructions for detour graphs of all orders greater than 17 and all detour deficiencies greater than zero. These constructions are used to give examples of nontraceable detour graphs with chromatic number \(k\geq 2\) and girths up to 7. In addition, the authors show that for all integers \(d\geq 1\) and \(k\geq 3\) there exist nontraceable detour graphs with chromatic number \(k\) and detour deficiency \(d\). The paper concludes with some open problems.
0 references
detour order
0 references
detour sequence
0 references
longest path
0 references