# A note on maximal common subgraphs of the Dirac's family of graphs

Jozef Bucko; Peter Mihók; Jean-François Saclé; Mariusz Woźniak

Discussiones Mathematicae Graph Theory (2005)

- Volume: 25, Issue: 3, page 385-390
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topJozef Bucko, et al. "A note on maximal common subgraphs of the Dirac's family of graphs." Discussiones Mathematicae Graph Theory 25.3 (2005): 385-390. <http://eudml.org/doc/270422>.

@article{JozefBucko2005,

abstract = {Let ⁿ be a given set of unlabeled simple graphs of order n. A maximal common subgraph of the graphs of the set ⁿ is a common subgraph F of order n of each member of ⁿ, that is not properly contained in any larger common subgraph of each member of ⁿ. By well-known Dirac’s Theorem, the Dirac’s family ⁿ of the graphs of order n and minimum degree δ ≥ [n/2] has a maximal common subgraph containing Cₙ. In this note we study the problem of determining all maximal common subgraphs of the Dirac’s family $ ^\{2n\}$ for n ≥ 2.},

author = {Jozef Bucko, Peter Mihók, Jean-François Saclé, Mariusz Woźniak},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {maximal common subgraph; Dirac's family; Hamiltonian cycle},

language = {eng},

number = {3},

pages = {385-390},

title = {A note on maximal common subgraphs of the Dirac's family of graphs},

url = {http://eudml.org/doc/270422},

volume = {25},

year = {2005},

}

TY - JOUR

AU - Jozef Bucko

AU - Peter Mihók

AU - Jean-François Saclé

AU - Mariusz Woźniak

TI - A note on maximal common subgraphs of the Dirac's family of graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2005

VL - 25

IS - 3

SP - 385

EP - 390

AB - Let ⁿ be a given set of unlabeled simple graphs of order n. A maximal common subgraph of the graphs of the set ⁿ is a common subgraph F of order n of each member of ⁿ, that is not properly contained in any larger common subgraph of each member of ⁿ. By well-known Dirac’s Theorem, the Dirac’s family ⁿ of the graphs of order n and minimum degree δ ≥ [n/2] has a maximal common subgraph containing Cₙ. In this note we study the problem of determining all maximal common subgraphs of the Dirac’s family $ ^{2n}$ for n ≥ 2.

LA - eng

KW - maximal common subgraph; Dirac's family; Hamiltonian cycle

UR - http://eudml.org/doc/270422

ER -

## References

top- [1] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Macmillan, London; Elsevier, New York, 1976). Zbl1226.05083
- [2] G.A. Dirac, Some theorems on abstract graphs, Proc. London Math. Soc. (3) 2 (1952) 69-81, doi: 10.1112/plms/s3-2.1.69. Zbl0047.17001
- [3] V. Chvátal, New directions in Hamiltonian graph theory in: New Directions in the Theory of Graphs (Academic Press, New York, 1973) 65-95.
- [4] O. Ore, On a graph theorem by Dirac J. Combin. Theory 2 (1967) 383-392, doi: 10.1016/S0021-9800(67)80036-X.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.