DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

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

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 26(2) (2006) 307-316
DOI: 10.7151/dmgt.1322

GRAPHS WITH CONVEX DOMINATION NUMBER CLOSE TO THEIR ORDER

Joanna Cyman, Magdalena Lemańska and Joanna Raczek

Department of Technical Physics and Applied Mathematics
Gdańsk University of Technology
Narutowicza 11/12, 80-952 Gdańsk, Poland
e-mail: {joana, magda, gardenia}@mif.pg.gda.pl

Abstract

For a connected graph G = (V,E), a set D ⊆ V(G) is a dominating set of G if every vertex in V(G)−D has at least one neighbour in D. The distance dG(u,v) between two vertices u and v is the length of a shortest (u−v) path in G. An (u−v) path of length dG(u,v) is called an (u−v)-geodesic. A set X ⊆ V(G) is convex in G if vertices from all (a−b)-geodesics belong to X for any two vertices a,b ∈ X. A set X is a convex dominating set if it is convex and dominating. The convex domination number γcon(G) of a graph G is the minimum cardinality of a convex dominating set in G. Graphs with the convex domination number close to their order are studied. The convex domination number of a Cartesian product of graphs is also considered.

Keywords: convex domination, Cartesian product.

2000 Mathematics Subject Classification: 05C12, 05C69.

References

[1] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of domination in graphs (Marcel Dekker, Inc., 1998).
[2] Sergio R. Canoy Jr and I.J.L. Garces, Convex sets under some graphs operations, Graphs and Combinatorics 18 (2002) 787-793, doi: 10.1007/s003730200065.

Received 21 January 2005
Revised 18 November 2005