PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2005 | 25 | 3 | 385-390
Tytuł artykułu

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

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Wydawca
Rocznik
Tom
25
Numer
3
Strony
385-390
Opis fizyczny
Daty
wydano
2005
otrzymano
2004-06-22
poprawiono
2005-06-13
Twórcy
autor
  • Technical University of Košice, Faculty of Economics, Nĕmcovej 32, 040 01 Košice, Slovakia
autor
  • Technical University of Košice, Faculty of Economics, Nĕmcovej 32, 040 01 Košice, Slovakia
  • LRI, Bât. 490, Université de Paris-Sud, 91405 Orsay, France
  • AGH University of Science and Technology, Department of Applied Mathematics, Al. Mickiewicza 30, 30-059 Kraków, Poland
Bibliografia
  • [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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1290
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.