DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2019: 0.755

SCImago Journal Rank (SJR) 2019: 0.600

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

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory  17(1) (1997)   115-125
DOI: 10.7151/dmgt.1044

THE ORDER OF UNIQUELY PARTITIONABLE GRAPHS

Izak Broere

Department of Mathematics
Rand Afrikaans University
P.O. Box 524, Aucklandpark, 2006 South Africa
e-mail: ib@rau3.rau.ac.za

Marietjie Frick

Department of Mathematics, Applied Mathematics and Astronomy
University of South Africa
P.O. Box 392, Pretoria, 0001 South Africa
e-mail: frickm@alpha.unisa.ac.za

Peter Mihók

Department of Geometry and Algebra
P.J. Šafárik University
Jesenná 5, 041 54 Košice, Slovak Republic
e-mail: mihok@Košice.upjs.sk

Abstract

Let P1, ..., Pn be properties of graphs. A (P1, Ľ, Pn)-partition of a graph G is a partition {V1, ...,Vn} of V(G) such that, for each i = 1,..., n, the subgraph of G induced by Vi has property Pi. If a graph G has a unique (P1, ..., Pn)-partition we say it is uniquely (P1, ..., Pn)-partitionable. We establish best lower bounds for the order of uniquely (P1, ...,  Pn)-partitionable graphs, for various choices of P1, ..., Pn.

Keywords: hereditary property of graphs, uniquely partitionable graphs.

1991 Mathematics Subject Classification: 05C15, 05C70.

References

[1]

G. Benadé, I. Broere, B. Jonck and M. Frick, Uniquely (m,k)τ-colourable graphs and k-τ-saturated graphs, Discrete Math. 162 (1996) 13-22, doi: 10.1016/0012-365X(95)00301-C.

[2]

M. Borowiecki, P. Mihók, Hereditary properties of graphs, in: Advances in Graph Theory (Vishwa Internat. Publ., 1991) 41-68.

[3]

I. Broere and M. Frick, On the order of uniquely (k,m)-colourable graphs, Discrete Math. 82 (1990) 225-232, doi: 10.1016/0012-365X(90)90200-2.

[4]

I. Broere, M. Frick and G. Semanišin, Maximal graphs with respect to hereditary properties, Discussiones Mathematicae Graph Theory 17 (1997) 51-66, doi: 10.7151/dmgt.1038.

[5]

G. Chartrand and L. Lesniak, Graphs and Digraphs (Second Edition, Wadsworth & Brooks/Cole, Monterey, 1986).

[6]

M. Frick, On replete graphs, J. Graph Theory 16 (1992) 165-175, doi: 10.1002/jgt.3190160208.

[7]

M. Frick and M.A. Henning, Extremal results on defective colourings of graphs, Discrete Math. 126 (1994) 151-158, doi: 10.1016/0012-365X(94)90260-7.

[8]

P. Mihók, Additive hereditary properties and uniquely partitionable graphs, in: Graphs, Hypergraphs and Matroids (Zielona Góra, 1985) 49-58.

[9]

P. Mihók and G. Semanišin, Reducible properties of graphs, Discussiones Math. Graph Theory 15 (1995) 11-18, doi: 10.7151/dmgt.1002.