Bounds on the global offensive k-alliance number in graphs

Mustapha Chellali; Teresa W. Haynes; Bert Randerath; Lutz Volkmann

Displaying similar documents to “Bounds on the global offensive k-alliance number in graphs”

A new look at an old comparison theorem

Jaroslav Jaroš (2021)

Archivum Mathematicum

Similarity:

We present an integral comparison theorem which guarantees the global existence of a solution of the generalized Riccati equation on the given interval $[a, b)$ when it is known that certain majorant Riccati equation has a global solution on $[a, b)$ .

On 𝓕-independence in graphs

Frank Göring, Jochen Harant, Dieter Rautenbach, Ingo Schiermeyer (2009)

Discussiones Mathematicae Graph Theory

Similarity:

Let be a set of graphs and for a graph G let $α_{} (G)$ and $α *_{} (G)$ denote the maximum order of an induced subgraph of G which does not contain a graph in as a subgraph and which does not contain a graph in as an induced subgraph, respectively. Lower bounds on $α_{} (G)$ and $α *_{} (G)$ are presented.

Fractional global domination in graphs

Subramanian Arumugam, Kalimuthu Karuppasamy, Ismail Sahul Hamid (2010)

Discussiones Mathematicae Graph Theory

Similarity:

Let G = (V,E) be a graph. A function g:V → [0,1] is called a global dominating function (GDF) of G, if for every v ∈ V, $g (N [v]) = \sum_{u \in N [v]} g (u) \geq 1$ and $g (\bar{N (v)}) = \sum_{u \notin N (v)} g (u) \geq 1$ . A GDF g of a graph G is called minimal (MGDF) if for all functions f:V → [0,1] such that f ≤ g and f(v) ≠ g(v) for at least one v ∈ V, f is not a GDF. The fractional global domination number $γ_{f g} (G)$ is defined as follows: $γ_{f g} (G)$ = min|g|:g is an MGDF of G where $| g | = \sum_{v \in V} g (v)$ . In this paper we initiate a study of this parameter.

Upper oriented chromatic number of undirected graphs and oriented colorings of product graphs

Éric Sopena (2012)

Discussiones Mathematicae Graph Theory

Similarity:

The oriented chromatic number of an oriented graph $^{\to} G$ is the minimum order of an oriented graph $^{\to} H$ such that $^{\to} G$ admits a homomorphism to $^{\to} H$ . The oriented chromatic number of an undirected graph G is then the greatest oriented chromatic number of its orientations. In this paper, we introduce the new notion of the upper oriented chromatic number of an undirected graph G, defined as the minimum order of an oriented graph $^{\to} U$ such that every orientation $^{\to} G$ of G admits a homomorphism to $^{\to} U$ . We give...

Upper bounds for the domination numbers of toroidal queens graphs

Christina M. Mynhardt (2003)

Discussiones Mathematicae Graph Theory

Similarity:

We determine upper bounds for $γ (Q n^{t})$ and $i (Q ₙ^{t})$ , the domination and independent domination numbers, respectively, of the graph $Q ₙ^{t}$ obtained from the moves of queens on the n×n chessboard drawn on the torus.

On subgraphs without large components

Glenn G. Chappell, John Gimbel (2017)

Mathematica Bohemica

Similarity:

We consider, for a positive integer $k$ , induced subgraphs in which each component has order at most $k$ . Such a subgraph is said to be $k$ -divided. We show that finding large induced subgraphs with this property is NP-complete. We also consider a related graph-coloring problem: how many colors are required in a vertex coloring in which each color class induces a $k$ -divided subgraph. We show that the problem of determining whether some given number of colors suffice is NP-complete, even for...

On distinguishing and distinguishing chromatic numbers of hypercubes

Werner Klöckl (2008)

Discussiones Mathematicae Graph Theory

Similarity:

The distinguishing number D(G) of a graph G is the least integer d such that G has a labeling with d colors that is not preserved by any nontrivial automorphism. The restriction to proper labelings leads to the definition of the distinguishing chromatic number $χ_{D} (G)$ of G. Extending these concepts to infinite graphs we prove that $D (Q_{ℵ} ₀) = 2$ and $χ_{D} (Q_{ℵ} ₀) = 3$ , where $Q_{ℵ} ₀$ denotes the hypercube of countable dimension. We also show that $χ_{D} (Q ₄) = 4$ , thereby completing the investigation of finite hypercubes with respect to $χ_{D}$ . Our...

On the total k-domination number of graphs

Adel P. Kazemi (2012)

Discussiones Mathematicae Graph Theory

Similarity:

Let k be a positive integer and let G = (V,E) be a simple graph. The k-tuple domination number $γ_{\times k} (G)$ of G is the minimum cardinality of a k-tuple dominating set S, a set that for every vertex v ∈ V, $| N_{G} [v] \cap S | \geq k$ . Also the total k-domination number $γ_{\times k, t} (G)$ of G is the minimum cardinality of a total k -dominating set S, a set that for every vertex v ∈ V, $| N_{G} (v) \cap S | \geq k$ . The k-transversal number τₖ(H) of a hypergraph H is the minimum size of a subset S ⊆ V(H) such that |S ∩e | ≥ k for every edge e ∈ E(H). We know that for...

Proper connection number of bipartite graphs

Jun Yue, Meiqin Wei, Yan Zhao (2018)

Czechoslovak Mathematical Journal

Similarity:

An edge-colored graph $G$ is proper connected if every pair of vertices is connected by a proper path. The proper connection number of a connected graph $G$ , denoted by $pc (G)$ , is the smallest number of colors that are needed to color the edges of $G$ in order to make it proper connected. In this paper, we obtain the sharp upper bound for $pc (G)$ of a general bipartite graph $G$ and a series of extremal graphs. Additionally, we give a proper $2$ -coloring for a connected bipartite graph $G$ having $δ (G) \geq 2$ and a dominating...

Edit distance measure for graphs

Tomasz Dzido, Krzysztof Krzywdziński (2015)

Czechoslovak Mathematical Journal

Similarity:

In this paper, we investigate a measure of similarity of graphs similar to the Ramsey number. We present values and bounds for $g (n, l)$ , the biggest number $k$ guaranteeing that there exist $l$ graphs on $n$ vertices, each two having edit distance at least $k$ . By edit distance of two graphs $G$ , $F$ we mean the number of edges needed to be added to or deleted from graph $G$ to obtain graph $F$ . This new extremal number $g (n, l)$ is closely linked to the edit distance of graphs. Using probabilistic methods we show...

On characterization of uniquely 3-list colorable complete multipartite graphs

Yancai Zhao, Erfang Shan (2010)

Discussiones Mathematicae Graph Theory

Similarity:

For each vertex v of a graph G, if there exists a list of k colors, L(v), such that there is a unique proper coloring for G from this collection of lists, then G is called a uniquely k-list colorable graph. Ghebleh and Mahmoodian characterized uniquely 3-list colorable complete multipartite graphs except for nine graphs: $K_{2, 2, r}$ r ∈ 4,5,6,7,8, $K_{2, 3, 4}$ , $K_{1 * 4, 4}$ , $K_{1 * 4, 5}$ , $K_{1 * 5, 4}$ . Also, they conjectured that the nine graphs are not U3LC graphs. After that, except for $K_{2, 2, r}$ r ∈ 4,5,6,7,8, the others have been proved not...

Note on improper coloring of $1$ -planar graphs

Yanan Chu, Lei Sun, Jun Yue (2019)

Czechoslovak Mathematical Journal

Similarity:

A graph $G = (V, E)$ is called improperly $(d_{1}, \dots, d_{k})$ -colorable if the vertex set $V$ can be partitioned into subsets $V_{1}, \dots, V_{k}$ such that the graph $G [V_{i}]$ induced by the vertices of $V_{i}$ has maximum degree at most $d_{i}$ for all $1 \leq i \leq k$ . In this paper, we mainly study the improper coloring of $1$ -planar graphs and show that $1$ -planar graphs with girth at least $7$ are $(2, 0, 0, 0)$ -colorable.

Remarks on $D$ -integral complete multipartite graphs

Pavel Híc, Milan Pokorný (2016)

Czechoslovak Mathematical Journal

Similarity:

A graph is called distance integral (or $D$ -integral) if all eigenvalues of its distance matrix are integers. In their study of $D$ -integral complete multipartite graphs, Yang and Wang (2015) posed two questions on the existence of such graphs. We resolve these questions and present some further results on $D$ -integral complete multipartite graphs. We give the first known distance integral complete multipartite graphs $K_{p_{1}, p_{2}, p_{3}}$ with $p_{1} < p_{2} < p_{3}$ , and $K_{p_{1}, p_{2}, p_{3}, p_{4}}$ with $p_{1} < p_{2} < p_{3} < p_{4}$ , as well as the infinite classes of distance integral...