DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 25(3) (2005) 385-390
DOI: 10.7151/dmgt.1290

A NOTE ON MAXIMAL COMMON SUBGRAPHS OF THE DIRAC'S FAMILY OF GRAPHS

Jozef Bucko and Peter Mihók

Technical University of Košice
Faculty of Economics
Nemcovej 32, 040 01 Košice, Slovakia
e-mail: jozef.bucko@tuke.sk
e-mail: peter.mihok@tuke.sk

Jean-François Saclé

LRI, Bât. 490, Université de Paris-Sud
91405 Orsay, France
e-mail: sacle@lri.fr

Mariusz Woźniak

AGH University of Science and Technology
Department of Applied Mathematics
Al. Mickiewicza 30, 30-059 Kraków, Poland
e-mail: mwozniak@agh.edu.pl

Abstract

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

Keywords: maximal common subgraph, Dirac's family, Hamiltonian cycle.

2000 Mathematics Subject Classification: 05C75, 05C45.

References

[1] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications (Macmillan, London; Elsevier, New York, 1976).
[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.
[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.

Received 22 June 2004
Revised 13 June 2005