Distance independence in graphs

J. Louis Sewell; Peter J. Slater

Discussiones Mathematicae Graph Theory (2011)

  • Volume: 31, Issue: 2, page 397-409
  • ISSN: 2083-5892

Abstract

top
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 β O D D ( G ) where ODD = 1,3,5,....

How to cite

top

J. Louis Sewell, and Peter J. Slater. "Distance independence in graphs." Discussiones Mathematicae Graph Theory 31.2 (2011): 397-409. <http://eudml.org/doc/270818>.

@article{J2011,
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,....},
author = {J. Louis Sewell, Peter J. Slater},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {independence number; distance set},
language = {eng},
number = {2},
pages = {397-409},
title = {Distance independence in graphs},
url = {http://eudml.org/doc/270818},
volume = {31},
year = {2011},
}

TY - JOUR
AU - J. Louis Sewell
AU - Peter J. Slater
TI - Distance independence in graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2011
VL - 31
IS - 2
SP - 397
EP - 409
AB - 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,....
LA - eng
KW - independence number; distance set
UR - http://eudml.org/doc/270818
ER -

References

top
  1. [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. Zbl0393.05044
  2. [2] T. Gallai, Über extreme Punkt-und Kantenmengen, Ann. Univ. Sci. Budapest, Eotvos Sect. Math. 2 (1959) 133-138. 
  3. [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 Zbl0997.05074
  4. [4] J.D. McFall and R. Nowakowski, Strong indepedence in graphs, Congr. Numer. 29 (1980) 639-656. 
  5. [5] J.L. Sewell, Distance Generalizations of Graphical Parameters, (Univ. Alabama in Huntsville, 2011). 
  6. [6] A. Sinko and P.J. Slater, Generalized graph parametric chains, submitted for publication. 
  7. [7] A. Sinko and P.J. Slater, R-parametric and R-chromatic problems, submitted for publication. 
  8. [8] P.J. Slater, Enclaveless sets and MK-systems, J. Res. Nat. Bur. Stan. 82 (1977) 197-202. Zbl0421.05053
  9. [9] P.J. Slater, Generalized graph parametric chains, in: Combinatorics, Graph Theory and Algorithms (New Issues Press, Western Michigan University 1999) 787-797. 
  10. [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. Zbl0980.05038
  11. [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. Zbl1020.05051
  12. [12] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, LP-duality, complementarity and generality of graphical subset problems, in: Domination in Graphs Advanced Topics, T.W. Haynes et al. (eds) (Marcel-Dekker, Inc. 1998) 1-30. 

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.