Hamiltonian threshold graphs
type: Item
instance of: scholarly article
title: Hamiltonian threshold graphs
zbMATH Open document ID: 0601.05033
DOI: 10.1016/0166-218X(87)90050-3
author: Frank Harary
author: Uri N. Peled
published in: Discrete Applied Mathematics
publication date: 1987-01-01T00:00:00Z
review text: The vertices of a threshold graph G are partitioned into a clique K and an independent set I so that the neighborhoods of the vertices of I are totally ordered by inclusion. The question of whether G is hamiltonian is reduced to the case that K and I have the same size, say r, in which case the edges of K do not affect the answer and may be dropped from G, yielding a bipartite graph B. Let \(d_ 1\leq d_ 2\leq...\leq d_ r\) and \(e_ 1\leq e_ 2\leq...\leq e_ r\) be the degrees in B of the vertices of I and K, respectively. For each \(q=0,1,...,r-1\), denote by \(S_ q\) the following system of inequalities: a) \(d_ j\geq j+1\), \(j=1,2,...,q\), and b) \(e_ j\geq j+1\), \(j=1,2,...,r- q-1.\) Then the following conditions are equivalent: (1) B is hamiltonian, (2) \(S_ q\) holds for some \(q=0,1,...,r-1\), (3) \(S_ q\) holds for each \(q=0,1,...,r-1\).
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 3968622
zbMATH Keywords: hamiltonicity
zbMATH Keywords: threshold graph
zbMATH Keywords: clique
zbMATH Keywords: independent set I
MaRDI profile type: Publication
cites work: A note on Hamiltonian split graphs
cites work: On Hamilton's ideals
cites work: Q4165164
cites work: Q3328583
cites work: Threshold Sequences
cites work: Parallel concepts in graph theory
cites work: On Hamiltonian bipartite graphs
cites work: Necessary conditions for Hamiltonian split graphs
Recommended article: Notes on Hamiltonian threshold and chain graphs
Recommended article: Hamiltonian-connected graphs
Recommended article: Hamiltonian threshold for strong products of graphs
Recommended article: Threshold hypergraphs
Recommended article: Hamiltonian Kneser graphs
Recommended article: Threshold graphs
Recommended article: Q3356326
Recommended article: On hamiltonian‐connected graphs
Recommended article: Hamiltonian jump graphs
description: scientific article; zbMATH DE number 3968622