ArticleOriginal scientific text

Title

Graphs with convex domination number close to their order

Authors 1, 1, 1

Affiliations

  1. Department of Technical Physics and Applied Mathematics, Gdańsk University of Technology, Narutowicza 11/12, 80-952 Gdańsk, Poland

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

Bibliography

  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.
Pages:
307-316
Main language of publication
English
Received
2005-01-21
Accepted
2005-11-18
Published
2006
Exact and natural sciences