Strong equality of upper domination and independence in trees

Teresa W. Haynes; Michael A. Henning; Peter J. Slater

Strong equality of upper domination and independence in trees

Teresa W. Haynes, Michael A. Henning, Peter J. Slater

Research output: Contribution to journal › Article › peer-review

6 Citations (Scopus)

Abstract

Let P₁ and P₂ be properties of vertex subsets of a graph G, and assume that every subset of V (G) with property P₂ also has property P₁. Let μ₁(G) and μ₂(G), respectively, denote the maximum cardinalities of sets with properties P₁ and P₂, respectively. Then μ₁(G) ≥ μ₂(G). If μ₁(G) = μ₂(G) and every μ₁(G)-set is also a μ₂(G)-set, then we say μ₁(G) strongly equals μ₂(G), written μ₁(G) ≡ μ₂(G). We provide a constructive characterization of the trees T such that Γ(T) ≡ β(T), where β(T) and Γ(T) are the independence and upper domination numbers of T, respectively.

Original language	English
Pages (from-to)	111-124
Number of pages	14
Journal	Utilitas Mathematica
Volume	59
Publication status	Published - May 2001
Externally published	Yes

ASJC Scopus subject areas

Statistics and Probability
Statistics, Probability and Uncertainty
Applied Mathematics

Cite this

@article{9710ffe7ff8149c6ad680668e6e01924,

title = "Strong equality of upper domination and independence in trees",

abstract = "Let P1 and P2 be properties of vertex subsets of a graph G, and assume that every subset of V (G) with property P2 also has property P1. Let μ1(G) and μ2(G), respectively, denote the maximum cardinalities of sets with properties P1 and P2, respectively. Then μ1(G) ≥ μ2(G). If μ1(G) = μ2(G) and every μ1(G)-set is also a μ2(G)-set, then we say μ1(G) strongly equals μ2(G), written μ1(G) ≡ μ2(G). We provide a constructive characterization of the trees T such that Γ(T) ≡ β(T), where β(T) and Γ(T) are the independence and upper domination numbers of T, respectively.",

author = "Haynes, {Teresa W.} and Henning, {Michael A.} and Slater, {Peter J.}",

year = "2001",

month = may,

language = "English",

volume = "59",

pages = "111--124",

journal = "Utilitas Mathematica",

issn = "0315-3681",

publisher = "Utilitas Mathematica Publishing Inc.",

}

TY - JOUR

T1 - Strong equality of upper domination and independence in trees

AU - Haynes, Teresa W.

AU - Henning, Michael A.

AU - Slater, Peter J.

PY - 2001/5

Y1 - 2001/5

N2 - Let P1 and P2 be properties of vertex subsets of a graph G, and assume that every subset of V (G) with property P2 also has property P1. Let μ1(G) and μ2(G), respectively, denote the maximum cardinalities of sets with properties P1 and P2, respectively. Then μ1(G) ≥ μ2(G). If μ1(G) = μ2(G) and every μ1(G)-set is also a μ2(G)-set, then we say μ1(G) strongly equals μ2(G), written μ1(G) ≡ μ2(G). We provide a constructive characterization of the trees T such that Γ(T) ≡ β(T), where β(T) and Γ(T) are the independence and upper domination numbers of T, respectively.

AB - Let P1 and P2 be properties of vertex subsets of a graph G, and assume that every subset of V (G) with property P2 also has property P1. Let μ1(G) and μ2(G), respectively, denote the maximum cardinalities of sets with properties P1 and P2, respectively. Then μ1(G) ≥ μ2(G). If μ1(G) = μ2(G) and every μ1(G)-set is also a μ2(G)-set, then we say μ1(G) strongly equals μ2(G), written μ1(G) ≡ μ2(G). We provide a constructive characterization of the trees T such that Γ(T) ≡ β(T), where β(T) and Γ(T) are the independence and upper domination numbers of T, respectively.

UR - http://www.scopus.com/inward/record.url?scp=0035592072&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:0035592072

SN - 0315-3681

VL - 59

SP - 111

EP - 124

JO - Utilitas Mathematica

JF - Utilitas Mathematica

ER -

Strong equality of upper domination and independence in trees

Abstract

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this