TITLE

TREES WITH EQUAL 2-DOMINATION AND 2-INDEPENDENCE NUMBERS

AUTHOR(S)
CHELLALI, MUSTAPHA; MEDDAH, NACÉRA
PUB. DATE
May 2012
SOURCE
Discussiones Mathematicae: Graph Theory;2012, Vol. 32 Issue 2, p263
SOURCE TYPE
Academic Journal
DOC. TYPE
Article
ABSTRACT
Let G = (V,E) be a graph. A subset S of V is a 2-dominating set if every vertex of V - S is dominated at least 2 times, and S is a 2-independent set of G if every vertex of S has at most one neighbor in S. The minimum car- dinality of a 2-dominating set a of G is the 2-domination number γ2(G) and the maximum cardinality of a 2-independent set of G is the 2-independence number β2(G). Fink and Jacobson proved that γ2(G) ≤ β2(G) for every graph G. In this paper we provide a constructive characterization of trees with equal 2-domination and 2-independence numbers.
ACCESSION #
86440291

 

Related Articles

  • A CHARACTERIZATION OF TREES FOR A NEW LOWER BOUND ON THE k-INDEPENDENCE NUMBER. MEDDAH, NACÉRA; BLIDIA, MOSTAFA // Discussiones Mathematicae: Graph Theory;2013, Vol. 33 Issue 2, p395 

    Let k be a positive integer and G = (V,E) a graph of order n. A subset S of V is a k-independent set of G if the maximum degree of the subgraph induced by the vertices of S is less or equal to k - 1. The maximum cardinality of a k-independent set of G is the k-independence number βκ(G). In...

  • GRAPHS WITH EQUAL DOMINATION AND 2-DISTANCE DOMINATION NUMBERS. RACZEK, JOANNA // Discussiones Mathematicae: Graph Theory;2011, Vol. 31 Issue 2, p375 

    No abstract available.

  • STRONG EQUALITY BETWEEN THE ROMAN DOMINATION AND INDEPENDENT ROMAN DOMINATION NUMBERS IN TREES. CHELLALI, MUSTAPHA; RAD, NADER JAFARI // Discussiones Mathematicae: Graph Theory;2013, Vol. 33 Issue 2, p337 

    A Roman dominating function (RDF) on a graph G = (V, E) is a function f : V → {0, 1, 2} satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. The weight of an RDF is the value f(V (G)) = Σu ∈ V(G) f(u). An RDF f in...

  • EDGE DOMINATING SETS AND VERTEX COVERS. DUTTON, RONALD; KLOSTERMEYER, WILLIAM F. // Discussiones Mathematicae: Graph Theory;2013, Vol. 33 Issue 2, p437 

    Bipartite graphs with equal edge domination number and maximum matching cardinality are characterized. These two parameters are used to develop bounds on the vertex cover and total vertex cover numbers of graphs and a resulting chain of vertex covering, edge domination, and matching parameters...

  • On graphs whose chromatic transversal number is two. Ayyaswamy, S. K.; Natarajan, C. // Proyecciones - Journal of Mathematics;2011, Vol. 30 Issue 1, p59 

    In this paper we characterize the class of trees, block graphs, cactus graphs and cubic graphs for which the chromatic transversal domination number is equal to two.

  • WEAK ROMAN DOMINATION IN GRAPHS. PUSHPAM, P. ROUSHINI LEELY; MAI, T. N. M. MALINI // Discussiones Mathematicae: Graph Theory;2011, Vol. 31 Issue 1, p115 

    No abstract available.

  • A CHARACTERIZATION OF LOCATING-TOTAL DOMINATION EDGE CRITICAL GRAPHS. BLIDIA, MOSTAFA; DALI, WIDAD // Discussiones Mathematicae: Graph Theory;2011, Vol. 31 Issue 1, p197 

    No abstract available.

  • PAIRED DOMINATION IN PRISMS OF GRAPHS. MYNHARDT, CHRISTINA M.; SCHURCH, MARK // Discussiones Mathematicae: Graph Theory;2011, Vol. 31 Issue 1, p5 

    No abstract available.

  • NORMAL SPANNING TREES, ARONSZAJN TREES AND EXCLUDED MINORS. DIESTEL, REINHARD; LEADER, IMRE // Journal of the London Mathematical Society;02/01/2001, Vol. 63 Issue 1, p16 

    It is proved that a connected infinite graph has a normal spanning tree (the infinite analogue of a depth-first search tree) if and only if it has no minor obtained canonically from either an (50, 51)-regular bipartite graph or an order-theoretic Aronszajn tree. This disproves Halin's conjecture...

Share

Read the Article

Courtesy of VIRGINIA BEACH PUBLIC LIBRARY AND SYSTEM

Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics