Reducible properties of graphs

P. Mihók; G. Semanišin

Discussiones Mathematicae Graph Theory (1995)

  • Volume: 15, Issue: 1, page 11-18
  • ISSN: 2083-5892

Abstract

top
Let L be the set of all hereditary and additive properties of graphs. For P₁, P₂ ∈ L, the reducible property R = P₁∘P₂ is defined as follows: G ∈ R if and only if there is a partition V(G) = V₁∪ V₂ of the vertex set of G such that ⟨ V ₁ ⟩ G ∈ P ₁ and ⟨ V ₂ ⟩ G ∈ P ₂ . The aim of this paper is to investigate the structure of the reducible properties of graphs with emphasis on the uniqueness of the decomposition of a reducible property into irreducible ones.

How to cite

top

P. Mihók, and G. Semanišin. "Reducible properties of graphs." Discussiones Mathematicae Graph Theory 15.1 (1995): 11-18. <http://eudml.org/doc/270454>.

@article{P1995,
abstract = {Let L be the set of all hereditary and additive properties of graphs. For P₁, P₂ ∈ L, the reducible property R = P₁∘P₂ is defined as follows: G ∈ R if and only if there is a partition V(G) = V₁∪ V₂ of the vertex set of G such that $⟨V₁⟩_G ∈ P₁$ and $⟨V₂⟩_G ∈ P₂$. The aim of this paper is to investigate the structure of the reducible properties of graphs with emphasis on the uniqueness of the decomposition of a reducible property into irreducible ones.},
author = {P. Mihók, G. Semanišin},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {hereditary property of graphs; additivity; reducibility; additive properties of graphs; reducible property; hereditary property; cancellation problem},
language = {eng},
number = {1},
pages = {11-18},
title = {Reducible properties of graphs},
url = {http://eudml.org/doc/270454},
volume = {15},
year = {1995},
}

TY - JOUR
AU - P. Mihók
AU - G. Semanišin
TI - Reducible properties of graphs
JO - Discussiones Mathematicae Graph Theory
PY - 1995
VL - 15
IS - 1
SP - 11
EP - 18
AB - Let L be the set of all hereditary and additive properties of graphs. For P₁, P₂ ∈ L, the reducible property R = P₁∘P₂ is defined as follows: G ∈ R if and only if there is a partition V(G) = V₁∪ V₂ of the vertex set of G such that $⟨V₁⟩_G ∈ P₁$ and $⟨V₂⟩_G ∈ P₂$. The aim of this paper is to investigate the structure of the reducible properties of graphs with emphasis on the uniqueness of the decomposition of a reducible property into irreducible ones.
LA - eng
KW - hereditary property of graphs; additivity; reducibility; additive properties of graphs; reducible property; hereditary property; cancellation problem
UR - http://eudml.org/doc/270454
ER -

References

top
  1. [1] V. E. Alekseev, Range of values of entropy of hereditary classes of graphs, Diskretnaja matematika 4 (1992) 148-157 (Russian). Zbl0766.05088
  2. [2] M. Borowiecki, P. Mihók, Hereditary properties of graphs in: Advances in Graph Theory, Vishwa International Publication, India, (1991) 42-69. 
  3. [3] G. Chartrand, L. Lesniak, Graphs and Digraphs (Wadsworth & Brooks/Cole, Monterey California 1986). Zbl0666.05001
  4. [4] P. Mihók, Additive hereditary properties and uniquely partitionable graphs, in: Graphs, Hypergraphs and Matroids (Zielona Góra, 1985) 49-58. Zbl0623.05043
  5. [5] P. Mihók, An extension of Brook's theorem, Annals of Discrete Math. 51 (1992) 235-236. Zbl0766.05028
  6. [6] P. Mihók, On the minimal reducible bound for outerplanar and planar graphs, (to appear). Zbl0911.05043
  7. [7] M. Simonovits, Extremal graph theory, in: L. W. Beineke and R. J. Wilson eds. Selected Topics in Graph Theory 2 (Academic Press, London, 1983) 161-200. 
  8. [8] E. R. Scheinerman, On the structure of hereditary classes of graphs, Journal of Graph Theory 10 (1986) 545-551, doi: 10.1002/jgt.3190100414. Zbl0609.05057
  9. [9] E. R. Scheinerman, J. Zito, On the size of hereditary classes of graphs, J. Combin. Theory (B) 61 (1994) 16-39, doi: 10.1006/jctb.1994.1027. Zbl0811.05048

Citations in EuDML Documents

top
  1. P. Mihók, R. Vasky, On the factorization of reducible properties of graphs into irreducible factors
  2. Jan Kratochvíl, Peter Mihók, Gabriel Semanišin, Graphs maximal with respect to hom-properties
  3. Izak Broere, Marietjie Frick, Peter Mihók, The order of uniquely partitionable graphs
  4. Mieczysław Borowiecki, Anna Fiedorowicz, On partitions of hereditary properties of graphs
  5. Izak Broere, Marietjie Frick, Gabriel Semanišin, Maximal graphs with respect to hereditary properties
  6. Gabriel Semanišin, On some variations of extremal graph problems
  7. Izak Broere, Samuel John Teboho Moagi, Peter Mihók, Roman Vasky, Factorizations of properties of graphs
  8. Mieczysław Borowiecki, Izak Broere, Marietjie Frick, Peter Mihók, Gabriel Semanišin, A survey of hereditary properties of graphs

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.