Generalised irredundance in graphs: Nordhaus-Gaddum bounds

Ernest J. Cockayne; Stephen Finbow

Discussiones Mathematicae Graph Theory (2004)

  • Volume: 24, Issue: 1, page 147-160
  • ISSN: 2083-5892

Abstract

top
For each vertex s of the vertex subset S of a simple graph G, we define Boolean variables p = p(s,S), q = q(s,S) and r = r(s,S) which measure existence of three kinds of S-private neighbours (S-pns) of s. A 3-variable Boolean function f = f(p,q,r) may be considered as a compound existence property of S-pns. The subset S is called an f-set of G if f = 1 for all s ∈ S and the class of f-sets of G is denoted by Ω f ( G ) . Only 64 Boolean functions f can produce different classes Ω f ( G ) , special cases of which include the independent sets, irredundant sets, open irredundant sets and CO-irredundant sets of G. Let Q f ( G ) be the maximum cardinality of an f-set of G. For each of the 64 functions f, we establish sharp upper bounds for the sum Q f ( G ) + Q f ( G ̅ ) and the product Q f ( G ) Q f ( G ̅ ) in terms of n, the order of G.

How to cite

top

Ernest J. Cockayne, and Stephen Finbow. "Generalised irredundance in graphs: Nordhaus-Gaddum bounds." Discussiones Mathematicae Graph Theory 24.1 (2004): 147-160. <http://eudml.org/doc/270673>.

@article{ErnestJ2004,
abstract = {For each vertex s of the vertex subset S of a simple graph G, we define Boolean variables p = p(s,S), q = q(s,S) and r = r(s,S) which measure existence of three kinds of S-private neighbours (S-pns) of s. A 3-variable Boolean function f = f(p,q,r) may be considered as a compound existence property of S-pns. The subset S is called an f-set of G if f = 1 for all s ∈ S and the class of f-sets of G is denoted by $Ω_f(G)$. Only 64 Boolean functions f can produce different classes $Ω_f(G)$, special cases of which include the independent sets, irredundant sets, open irredundant sets and CO-irredundant sets of G. Let $Q_f(G)$ be the maximum cardinality of an f-set of G. For each of the 64 functions f, we establish sharp upper bounds for the sum $Q_f(G) + Q_f(G̅)$ and the product $Q_f(G)Q_f(G̅)$ in terms of n, the order of G.},
author = {Ernest J. Cockayne, Stephen Finbow},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {graph; generalised irredundance; Nordhaus-Gaddum; irredundant; Boolean function},
language = {eng},
number = {1},
pages = {147-160},
title = {Generalised irredundance in graphs: Nordhaus-Gaddum bounds},
url = {http://eudml.org/doc/270673},
volume = {24},
year = {2004},
}

TY - JOUR
AU - Ernest J. Cockayne
AU - Stephen Finbow
TI - Generalised irredundance in graphs: Nordhaus-Gaddum bounds
JO - Discussiones Mathematicae Graph Theory
PY - 2004
VL - 24
IS - 1
SP - 147
EP - 160
AB - For each vertex s of the vertex subset S of a simple graph G, we define Boolean variables p = p(s,S), q = q(s,S) and r = r(s,S) which measure existence of three kinds of S-private neighbours (S-pns) of s. A 3-variable Boolean function f = f(p,q,r) may be considered as a compound existence property of S-pns. The subset S is called an f-set of G if f = 1 for all s ∈ S and the class of f-sets of G is denoted by $Ω_f(G)$. Only 64 Boolean functions f can produce different classes $Ω_f(G)$, special cases of which include the independent sets, irredundant sets, open irredundant sets and CO-irredundant sets of G. Let $Q_f(G)$ be the maximum cardinality of an f-set of G. For each of the 64 functions f, we establish sharp upper bounds for the sum $Q_f(G) + Q_f(G̅)$ and the product $Q_f(G)Q_f(G̅)$ in terms of n, the order of G.
LA - eng
KW - graph; generalised irredundance; Nordhaus-Gaddum; irredundant; Boolean function
UR - http://eudml.org/doc/270673
ER -

References

top
  1. [1] B. Bollobás and E.J. Cockayne, The irredundance number and maximum degree of a graph, Discrete Math. 69 (1984) 197-199. Zbl0539.05056
  2. [2] E.J. Cockayne, Generalized irredundance in graphs: hereditary properties and Ramsey numbers, J. Combin. Math. Combin. Comput. 31 (1999) 15-31. Zbl0952.05051
  3. [3] E.J. Cockayne, Nordhaus-Gaddum Results for Open Irredundance, J. Combin. Math. Combin. Comput., to appear. Zbl1038.05042
  4. [4] E.J. Cockayne, O. Favaron, P.J.P. Grobler, C.M. Mynhardt and J. Puech, Ramsey properties of generalised irredundant sets in graphs, Discrete Math. 231 (2001) 123-134, doi: 10.1016/S0012-365X(00)00311-3. Zbl0977.05089
  5. [5] E.J. Cockayne, O. Favaron, C.M. Mynhardt, Open irredundance and maximum degree in graphs (submitted). Zbl1207.05095
  6. [6] E.J. Cockayne, P.J.P. Grobler, S.T. Hedetniemi and A.A. McRae, What makes an irredundant set maximal? J. Combin. Math. Combin. Comput. 25 (1997) 213-223. Zbl0907.05032
  7. [7] E.J. Cockayne, S.T. Hedetniemi, D.J. Miller, Properties of hereditary hypergraphs and middle graphs, Canad. Math. Bull. 21 (1978) 261-268, doi: 10.4153/CMB-1978-079-5. Zbl0393.05044
  8. [8] E.J. Cockayne, G. MacGillvray, J. Simmons, CO-irredundant Ramsey numbers for graphs, J. Graph Theory 34 (2000) 258-268, doi: 10.1002/1097-0118(200008)34:4<258::AID-JGT2>3.0.CO;2-4 
  9. [9] E.J. Cockayne, D. McCrea, C.M. Mynhardt, Nordhaus-Gaddum results for CO-irredundance in graphs, Discrete Math. 211 (2000) 209-215, doi: 10.1016/S0012-365X(99)00282-4. Zbl0948.05037
  10. [10] E.J. Cockayne and C.M. Mynhardt, Irredundance and maximum degree in graphs, Combin. Prob. Comput. 6 (1997) 153-157, doi: 10.1017/S0963548396002891. Zbl0881.05068
  11. [11] E.J. Cockayne, C.M. Mynhardt, On the product of upper irredundance numbers of a graphs and its complement, Discrete Math. 76 (1988) 117-121, doi: 10.1016/0012-365X(89)90304-X. Zbl0672.05049
  12. [12] E.J. Cockayne, C.M. Mynhardt, J. Simmons, The CO-irredundent Ramsey number t(4,7), Utilitas Math. 57 (2000) 193-209. Zbl0956.05073
  13. [13] A.M. Farley and A. Proskurowski, Computing the maximum order of an open irredundant set in a tree, Congr. Numer. 41 (1984) 219-228. Zbl0546.05034
  14. [14] A.M. Farley and N. Schacham, Senders in broadcast networks: open irredundancy in graphs, Congr. Numer. 38 (1983) 47-57. 
  15. [15] O. Favaron, A note on the open irredundance in a graph, Congr. Numer. 66 (1988) 316-318. Zbl0673.05083
  16. [16] O. Favaron, A note on the irredundance number after vertex deletion, Discrete Math. 121 (1993) 51-54, doi: 10.1016/0012-365X(93)90536-3. Zbl0791.05095
  17. [17] M.R. Fellows, G.H. Fricke, S.T. Hedetniemi and D. Jacobs, The private neighbour cube, SIAM J. Discrete Math. 7 (1994) 41-47, doi: 10.1137/S0895480191199026. Zbl0795.05078
  18. [18] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs (Marcel Dekker, New York, 1998). Zbl0890.05002
  19. [19] S.T. Hedetniemi, D.P. Jacobs and R.C. Laskar, Inequalities involving the rank of a graph, J. Combin. Math. Combin. Comput. 6 (1989) 173-176. Zbl0732.05039
  20. [20] E.A. Nordhaus and J.W. Gaddum, On complementary graphs, Amer. Math. Monthly 63 (1956) 175-177, doi: 10.2307/2306658. Zbl0070.18503
  21. [21] J. Simmons, CO-irredundant Ramsey numbers for graphs (Master's Thesis, University of Victoria, 1998). 

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.