DMGT

Discussiones Mathematicae Graph Theory 31(2) (2011) 397-409
DOI: https://doi.org/10.7151/dmgt.1554

Distance Independence in Graphs

J. Louis Sewell

Department of Mathematical Sciences
University of Alabama in Huntsville
Huntsville, AL 35899 USA

Peter J. Slater

Department of Mathematical Sciences
and Computer Sciences Department
University of Alabama in Huntsville
Huntsville, AL 35899 USA

Abstract

For a set D of positive integers, we define a vertex set S ⊆ V(G) to be D-independent if u, v ∈ S implies the distance d(u, v) ∉ D. The D-independence number β_D(G) is the maximum cardinality of a D-independent set. In particular, the independence number β(G) = β_{1}(G). Along with general results we consider, in particular, the odd-independence number β_ODD(G) where ODD = {1,3,5,…}.

Keywords: independence number, distance set

2010 Mathematics Subject Classification: 05C12, 05C38, 05C69, 05C70, 05C76.

References

[1]	E.J. Cockayne, S.T. Hedetniemi, and D.J. Miller, Properties of hereditary hypergraphs and middle graphs, Canad. Math. Bull. 21 (1978) 461--468, doi: 10.4153/CMB-1978-079-5.
[2]	T. Gallai, Über extreme Punkt-und Kantenmengen, Ann. Univ. Sci. Budapest, Eotvos Sect. Math. 2 (1959) 133--138.
[3]	T.W. Haynes and P.J. Slater, Paired domination in graphs, Networks 32 (1998) 199--206, doi: 10.1002/(SICI)1097-0037(199810)32:3<199::AID-NET4>3.0.CO;2-F.
[4]	J.D. McFall and R. Nowakowski, Strong indepedence in graphs, Congr. Numer. 29 (1980) 639--656.
[5]	J.L. Sewell, Distance Generalizations of Graphical Parameters, (Univ. Alabama in Huntsville, 2011).
[6]	A. Sinko and P.J. Slater, Generalized graph parametric chains, submitted for publication.
[7]	A. Sinko and P.J. Slater, R-parametric and R-chromatic problems, submitted for publication.
[8]	P.J. Slater, Enclaveless sets and MK-systems, J. Res. Nat. Bur. Stan. 82 (1977) 197--202.
[9]	P.J. Slater, Generalized graph parametric chains, in: Combinatorics, Graph Theory and Algorithms (New Issues Press, Western Michigan University 1999) 787--797.
[10]	T.W. Haynes, M.A. Henning and P.J. Slater, Strong equality of upper domination and independence in trees, Util. Math. 59 (2001) 111--124.
[11]	T.W. Haynes, M.A. Henning and P.J. Slater, Strong equality of domination parameters in trees, Discrete Math. 260 (2003) 77--87, doi: 10.1016/S0012-365X(02)00451-X.

Received 4 January 2010
Revised 6 January 2011
Accepted 10 January 2011