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

Abstract

top
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 2 n for n ≥ 2.

How to cite

top

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

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.