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 for n ≥ 2.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1290,
author = {Jozef Bucko and Peter Mih\'ok and Jean-Fran\c cois Sacl\'e and Mariusz Wo\'zniak},
title = {A note on maximal common subgraphs of the Dirac's family of graphs},
journal = {Discussiones Mathematicae Graph Theory},
volume = {25},
year = {2005},
pages = {385-390},
zbl = {1103.05070},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1290}
}
Jozef Bucko; Peter Mihók; Jean-François Saclé; Mariusz Woźniak. A note on maximal common subgraphs of the Dirac's family of graphs. Discussiones Mathematicae Graph Theory, Tome 25 (2005) pp. 385-390. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1290/
[000] [1] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Macmillan, London; Elsevier, New York, 1976). | Zbl 1226.05083
[001] [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. | Zbl 0047.17001
[002] [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.
[003] [4] O. Ore, On a graph theorem by Dirac J. Combin. Theory 2 (1967) 383-392, doi: 10.1016/S0021-9800(67)80036-X.