Displaying similar documents to “On the Signed (Total) K-Independence Number in Graphs”

On dominating the Cartesian product of a graph and K₂

Bert L. Hartnell, Douglas F. Rall (2004)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper we consider the Cartesian product of an arbitrary graph and a complete graph of order two. Although an upper and lower bound for the domination number of this product follow easily from known results, we are interested in the graphs that actually attain these bounds. In each case, we provide an infinite class of graphs to show that the bound is sharp. The graphs that achieve the lower bound are of particular interest given the special nature of their dominating sets and...

Bounds on the Signed 2-Independence Number in Graphs

Lutz Volkmann (2013)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a finite and simple graph with vertex set V (G), and let f V (G) → {−1, 1} be a two-valued function. If ∑x∈N|v| f(x) ≤ 1 for each v ∈ V (G), where N[v] is the closed neighborhood of v, then f is a signed 2-independence function on G. The weight of a signed 2-independence function f is w(f) =∑v∈V (G) f(v). The maximum of weights w(f), taken over all signed 2-independence functions f on G, is the signed 2-independence number α2s(G) of G. In this work, we mainly present upper bounds...

New Bounds on the Signed Total Domination Number of Graphs

Seyyed Mehdi Hosseini Moghaddam, Doost Ali Mojdeh, Babak Samadi, Lutz Volkmann (2016)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper, we study the signed total domination number in graphs and present new sharp lower and upper bounds for this parameter. For example by making use of the classic theorem of Turán [8], we present a sharp lower bound on Kr+1-free graphs for r ≥ 2. Applying the concept of total limited packing we bound the signed total domination number of G with δ(G) ≥ 3 from above by [...] . Also, we prove that γst(T) ≤ n − 2(s − s′) for any tree T of order n, with s support vertices and...

Some results on total domination in direct products of graphs

Paul Dorbec, Sylvain Gravier, Sandi Klavžar, Simon Spacapan (2006)

Discussiones Mathematicae Graph Theory

Similarity:

Upper and lower bounds on the total domination number of the direct product of graphs are given. The bounds involve the {2}-total domination number, the total 2-tuple domination number, and the open packing number of the factors. Using these relationships one exact total domination number is obtained. An infinite family of graphs is constructed showing that the bounds are best possible. The domination number of direct products of graphs is also bounded from below.

Placing bipartite graphs of small size II

Beata Orchel (1996)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper we give all pairs of non mutually placeable (p,q)-bipartite graphs G and H such that 2 ≤ p ≤ q, e(H) ≤ p and e(G)+e(H) ≤ 2p+q-1.

Signed k-independence in graphs

Lutz Volkmann (2014)

Open Mathematics

Similarity:

Let k ≥ 2 be an integer. A function f: V(G) → −1, 1 defined on the vertex set V(G) of a graph G is a signed k-independence function if the sum of its function values over any closed neighborhood is at most k − 1. That is, Σx∈N[v] f(x) ≤ k − 1 for every v ∈ V(G), where N[v] consists of v and every vertex adjacent to v. The weight of a signed k-independence function f is w(f) = Σv∈V(G) f(v). The maximum weight w(f), taken over all signed k-independence functions f on G, is the signed k-independence...

A note on uniquely embeddable graphs

Mariusz Woźniak (1998)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a simple graph of order n and size e(G). It is well known that if e(G) ≤ n-2, then there is an embedding G into its complement [G̅]. In this note, we consider a problem concerning the uniqueness of such an embedding.

Union of Distance Magic Graphs

Sylwia Cichacz, Mateusz Nikodem (2017)

Discussiones Mathematicae Graph Theory

Similarity:

A distance magic labeling of a graph G = (V,E) with |V | = n is a bijection ℓ from V to the set {1, . . . , n} such that the weight w(x) = ∑y∈NG(x) ℓ(y) of every vertex x ∈ V is equal to the same element μ, called the magic constant. In this paper, we study unions of distance magic graphs as well as some properties of such graphs.

Labeled Embedding Of (n, n-2)-Graphs In Their Complements

M.-A. Tahraoui, E. Duchêne, H. Kheddouci (2017)

Discussiones Mathematicae Graph Theory

Similarity:

Graph packing generally deals with unlabeled graphs. In [4], the authors have introduced a new variant of the graph packing problem, called the labeled packing of a graph. This problem has recently been studied on trees [M.A. Tahraoui, E. Duchêne and H. Kheddouci, Labeled 2-packings of trees, Discrete Math. 338 (2015) 816-824] and cycles [E. Duchˆene, H. Kheddouci, R.J. Nowakowski and M.A. Tahraoui, Labeled packing of graphs, Australas. J. Combin. 57 (2013) 109-126]. In this note, we...

Generalized domination, independence and irredudance in graphs

Mieczysław Borowiecki, Danuta Michalak, Elżbieta Sidorowicz (1997)

Discussiones Mathematicae Graph Theory

Similarity:

The purpose of this paper is to present some basic properties of 𝓟-dominating, 𝓟-independent, and 𝓟-irredundant sets in graphs which generalize well-known properties of dominating, independent and irredundant sets, respectively.

Domination in functigraphs

Linda Eroh, Ralucca Gera, Cong X. Kang, Craig E. Larson, Eunjeong Yi (2012)

Discussiones Mathematicae Graph Theory

Similarity:

Let G₁ and G₂ be disjoint copies of a graph G, and let f:V(G₁) → V(G₂) be a function. Then a functigraph C(G,f) = (V,E) has the vertex set V = V(G₁) ∪ V(G₂) and the edge set E = E(G₁) ∪ E(G₂) ∪ {uv | u ∈ V(G₁), v ∈ V(G₂),v = f(u)}. A functigraph is a generalization of a permutation graph (also known as a generalized prism) in the sense of Chartrand and Harary. In this paper, we study domination in functigraphs. Let γ(G) denote the domination number of G. It is readily seen that γ(G)...

A Note on the Locating-Total Domination in Graphs

Mirka Miller, R. Sundara Rajan, R. Jayagopal, Indra Rajasingh, Paul Manuel (2017)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper we obtain a sharp (improved) lower bound on the locating-total domination number of a graph, and show that the decision problem for the locating-total domination is NP-complete.

Relations between the domination parameters and the chromatic index of a graph

Włodzimierz Ulatowski (2009)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper we show upper bounds for the sum and the product of the lower domination parameters and the chromatic index of a graph. We also present some families of graphs for which these upper bounds are achieved. Next, we give a lower bound for the sum of the upper domination parameters and the chromatic index. This lower bound is a function of the number of vertices of a graph and a new graph parameter which is defined here. In this case we also characterize graphs for which a respective...

2-distance 4-colorability of planar subcubic graphs with girth at least 22

Oleg V. Borodin, Anna O. Ivanova (2012)

Discussiones Mathematicae Graph Theory

Similarity:

The trivial lower bound for the 2-distance chromatic number χ₂(G) of any graph G with maximum degree Δ is Δ+1. It is known that χ₂ = Δ+1 if the girth g of G is at least 7 and Δ is large enough. There are graphs with arbitrarily large Δ and g ≤ 6 having χ₂(G) ≥ Δ+2. We prove the 2-distance 4-colorability of planar subcubic graphs with g ≥ 22.

Light Graphs In Planar Graphs Of Large Girth

Peter Hudák, Mária Maceková, Tomáš Madaras, Pavol Široczki (2016)

Discussiones Mathematicae Graph Theory

Similarity:

A graph H is defined to be light in a graph family 𝒢 if there exist finite numbers φ(H, 𝒢) and w(H, 𝒢) such that each G ∈ 𝒢 which contains H as a subgraph, also contains its isomorphic copy K with ΔG(K) ≤ φ(H, 𝒢) and ∑x∈V(K) degG(x) ≤ w(H, 𝒢). In this paper, we investigate light graphs in families of plane graphs of minimum degree 2 with prescribed girth and no adjacent 2-vertices, specifying several necessary conditions for their lightness and providing sharp bounds on φ and w...

The leafage of a chordal graph

In-Jen Lin, Terry A. McKee, Douglas B. West (1998)

Discussiones Mathematicae Graph Theory

Similarity:

The leafage l(G) of a chordal graph G is the minimum number of leaves of a tree in which G has an intersection representation by subtrees. We obtain upper and lower bounds on l(G) and compute it on special classes. The maximum of l(G) on n-vertex graphs is n - lg n - 1/2 lg lg n + O(1). The proper leafage l*(G) is the minimum number of leaves when no subtree may contain another; we obtain upper and lower bounds on l*(G). Leafage equals proper leafage on claw-free chordal graphs. We use...