Nontraceable detour graphs (Q868352): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(5 intermediate revisions by 4 users not shown) | |||
Property / author | |||
Property / author: Gabriel Semanisin / rank | |||
Property / author | |||
Property / author: Gabriel Semanisin / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.disc.2006.07.019 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1993040197 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A survey of hereditary properties of graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Detour Chromatic Numbers / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Smallest claw-free, 2-connected, nontraceable graphs and the construction of maximal nontraceable graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3937438 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Smallest maximally nonhamiltonian graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4943521 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3287781 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3230887 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On Detours in Graphs<sup>1</sup> / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Eccentric sequences in graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Degrees in Homogeneously Traceable Graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3942985 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3710548 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3487383 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5537559 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 15:24, 25 June 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
0 references