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

Józef Bućko | Zendy; Peter Mihók | Zendy; Jean-François Saclé | Zendy; Mariusz Woźniak | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

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

Author(s) -

Józef Bućko,

Peter Mihók,

Jean-François Saclé,

Mariusz Woźniak

Publication year - 2005

Publication title -

discussiones mathematicae graph theory

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.476

H-Index - 19

eISSN - 2083-5892

pISSN - 1234-3099

DOI - 10.7151/dmgt.1290

Subject(s) - mathematics , combinatorics , dirac (video compression format) , discrete mathematics , physics , neutrino , nuclear physics

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 DF of the graphs of order n and minimum degree δ ≥ n2 has a maximal common subgraph ∗Research supported by Slovak VEGA Grant 2/4134/24. 386 J. Bucko, P. Mihók, J.-F. Saclé and M. Woźniak containing Cn. In this note we study the problem of determining all maximal common subgraphs of the Dirac’s family DF for n ≥ 2.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research