A conjecture on the prevalence of cubic bridge graphs

Jerzy Filar; Michael Haythorpe; Giang Nguyen

doi:10.7151/dmgt.1485

A conjecture on the prevalence of cubic bridge graphs

Jerzy Filar, Michael Haythorpe, Giang Nguyen

Research output: Contribution to journal › Article › peer-review

5 Citations (Scopus)

Abstract

Almost all d-regular graphs are Hamiltonian, for d ≥ 3 [8]. In this note we conjecture that in a similar, yet somewhat different, sense almost all cubic non-Hamiltonian graphs are bridge graphs, and present supporting empirical results for this prevalence of the latter among all connected cubic non-Hamiltonian graphs.

Original language	English
Pages (from-to)	175-179
Number of pages	5
Journal	Discussiones Mathematicae. Graph Theory
Volume	30
Issue number	1
DOIs	https://doi.org/10.7151/dmgt.1485
Publication status	Published - 2010

Keywords

Cubic bridge graph
Hamiltonian graph
Non-Hamiltonian graph

Access to Document

10.7151/dmgt.1485

Cite this

@article{8dbb218d46604743817de73d99b7290d,

title = "A conjecture on the prevalence of cubic bridge graphs",

abstract = "Almost all d-regular graphs are Hamiltonian, for d ≥ 3 [8]. In this note we conjecture that in a similar, yet somewhat different, sense almost all cubic non-Hamiltonian graphs are bridge graphs, and present supporting empirical results for this prevalence of the latter among all connected cubic non-Hamiltonian graphs.",

keywords = "Cubic bridge graph, Hamiltonian graph, Non-Hamiltonian graph",

author = "Jerzy Filar and Michael Haythorpe and Giang Nguyen",

year = "2010",

doi = "10.7151/dmgt.1485",

language = "English",

volume = "30",

pages = "175--179",

journal = "Discussiones Mathematicae. Graph Theory",

issn = "1234-3099",

publisher = "University of Zielona Gora",

number = "1",

}

TY - JOUR

T1 - A conjecture on the prevalence of cubic bridge graphs

AU - Filar, Jerzy

AU - Haythorpe, Michael

AU - Nguyen, Giang

PY - 2010

Y1 - 2010

N2 - Almost all d-regular graphs are Hamiltonian, for d ≥ 3 [8]. In this note we conjecture that in a similar, yet somewhat different, sense almost all cubic non-Hamiltonian graphs are bridge graphs, and present supporting empirical results for this prevalence of the latter among all connected cubic non-Hamiltonian graphs.

AB - Almost all d-regular graphs are Hamiltonian, for d ≥ 3 [8]. In this note we conjecture that in a similar, yet somewhat different, sense almost all cubic non-Hamiltonian graphs are bridge graphs, and present supporting empirical results for this prevalence of the latter among all connected cubic non-Hamiltonian graphs.

KW - Cubic bridge graph

KW - Hamiltonian graph

KW - Non-Hamiltonian graph

UR - http://www.discuss.wmie.uz.zgora.pl/gt/30_1/gt30-779.htm

UR - http://www.scopus.com/inward/record.url?scp=77956550118&partnerID=8YFLogxK

U2 - 10.7151/dmgt.1485

DO - 10.7151/dmgt.1485

M3 - Article

SN - 1234-3099

VL - 30

SP - 175

EP - 179

JO - Discussiones Mathematicae. Graph Theory

JF - Discussiones Mathematicae. Graph Theory

IS - 1

ER -

A conjecture on the prevalence of cubic bridge graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this