Outer-2-independent domination in graphs

We initiate the study of outer-2-independent domination in graphs. An outer-2-independent dominating set of a graph G is a set D of vertices of G such that every vertex of V(G)?D has a neighbor in D and the maximum vertex degree of the subgraph induced by V(G)?D is at most one. The outer-2-independent domination number of a graph G is the minimum cardinality of an outer-2-independent dominating set of G. We show that if a graph has minimum degree at least two, then its outer-2-independent domination number equals the number of vertices minus the 2-independence number. Then we investigate the outer-2-independent domination in graphs with minimum degree one. We also prove the Vizing-type conjecture for outer-2-independent domination and disprove the Vizing-type conjecture for outer-connected domination.     

On trees with total domination number equal to edge-vertex domination number plus one

An edge e∈E(G) dominates a vertex v∈V(G) if e is incident with v or e is incident with a vertex adjacent to v. An edge-vertex dominating set of a graph G is a set D of edges of G such that every vertex of G is edge-vertex dominated by an edge of D. The edge-vertex domination number of a graph G is the minimum cardinality of an edge-vertex dominating set of G. A subset D?V(G) is a total dominating set of G if every vertex of G has a neighbor in D. The total domination number of G is the minimum cardinality of a total dominating set of G. We characterize all trees with total domination number equal to edge-vertex domination number plus one.     

Vertex-edge domination in graphs

In this paper we study graph parameters related to vertex-edge domination, where a vertex dominates the edges incident to it as well as the edges adjacent to these incident edges. First, we present new relationships relating the ve-domination to some other domination parameters, answering in the affirmative four open questions posed in the 2007 PhD thesis by Lewis. Then we provide an upper bound for the independent ve-domination number in terms of the ve-domination number for every nontrivial connected K_1,k-free graph, with k ≥ 3, and we show that the independent ve-domination number is bounded above by the domination number for every nontrivial tree. Finally, we establish an upper bound on the ve-domination number for connected C₅-free graphs, improving a recent bound given for trees.     

Total [1,2]-domination in Graphs

A subset S ? V in a graph G = (V,E) is a total [1, 2]-set if, for every vertex \( \upsilon \in V, 1 \leq\mid N (\upsilon)\cap S\mid\leq \). The minimum cardinality of a total [1, 2]-set of G is called the total [1, 2]-domination number, denoted by γ_t[1,2](^G).We establish two sharp upper bounds on the total [1,2]-domination number of a graph G in terms of its order and minimum degree, and characterize the corresponding extremal graphs achieving these bounds. Moreover, we give some sufficient conditions for a graph without total [1, 2]-set and for a graph with the same total [1, 2]-domination number, [1, 2]-domination number and domination number.     

A note on the independent domination number versus the domination number in bipartite graphs

Let γ(G) and i(G) be the domination number and the independent domination number of G, respectively. Rad and Volkmann posted a conjecture that i(G)/γ(G) ≤ Δ(G)/2 for any graph G, where Δ(G) is its maximum degree (see N. J. Rad, L. Volkmann (2013)). In this work, we verify the conjecture for bipartite graphs. Several graph classes attaining the extremal bound and graphs containing odd cycles with the ratio larger than Δ(G)/2 are provided as well.     

Improved bounds on the generalized acyclic chromatic number

An r-acyclic edge chromatic number of a graph G, denoted by a _r ^′ r(G), is the minimum number of colors used to produce an edge coloring of the graph such that adjacent edges receive different colors and every cycle C has at least min {|C|, r} colors. We prove that a _r ^′ r(G) ≤ (4r + 1)Δ(G), when the girth of the graph G equals to max{50, Δ(G)} and 4 ≤ r ≤ 7. If we relax the restriction of the girth to max {220, Δ(G)}, the upper bound of a _r ^′ r(G) is not larger than (2r + 5)Δ(G) with 4 ≤ r ≤ 10.     

Groups Satisfying the Two-Prime Hypothesis with a Composition Factor Isomorphic to PSL<Subscript>2</Subscript>(<Emphasis Type="Italic">q</Emphasis>) for <Emphasis Type="Italic">q</Emphasis> ⩾ 7

Let G be a finite group and write cd(G) for the degree set of the complex irreducible characters of G. The group G is said to satisfy the two-prime hypothesis if for any distinct degrees a, b 2 cd(G), the total number of (not necessarily different) primes of the greatest common divisor gcd(a, b) is at most 2. We prove an upper bound on the number of irreducible character degrees of a nonsolvable group that has a composition factor isomorphic to PSL₂(q) for q ? 7.     

Edge Roman Domination on Graphs

An edge Roman dominating function of a graph G is a function \(f:E(G) \rightarrow \{0,1,2\}\) satisfying the condition that every edge e with \(f(e)=0\) is adjacent to some edge \(e'\) with \(f(e')=2\). The edge Roman domination number of G, denoted by \(\gamma '_R(G)\), is the minimum weight \(w(f) = \sum _{e\in E(G)} f(e)\) of an edge Roman dominating function f of G. This paper disproves a conjecture of Akbari, Ehsani, Ghajar, Jalaly Khalilabadi and Sadeghian Sadeghabad stating that if G is a graph of maximum degree \(\Delta \) on n vertices, then \(\gamma _R'(G) \le \lceil \frac{\Delta }{\Delta +1} n \rceil \). While the counterexamples having the edge Roman domination numbers \(\frac{2\Delta -2}{2\Delta -1} n\), we prove that \(\frac{2\Delta -2}{2\Delta -1} n + \frac{2}{2\Delta -1}\) is an upper bound for connected graphs. Furthermore, we provide an upper bound for the edge Roman domination number of k-degenerate graphs, which generalizes results of Akbari, Ehsani, Ghajar, Jalaly Khalilabadi and Sadeghian Sadeghabad. We also prove a sharp upper bound for subcubic graphs. In addition, we prove that the edge Roman domination numbers of planar graphs on n vertices is at most \(\frac{6}{7}n\), which confirms a conjecture of Akbari and Qajar. We also show an upper bound for graphs of girth at least five that is 2-cell embeddable in surfaces of small genus. Finally, we prove an upper bound for graphs that do not contain \(K_{2,3}\) as a subdivision, which generalizes a result of Akbari and Qajar on outerplanar graphs.     

A cycle cover of a 2-edge-connected graph embedded with large face-width on an orientable surface

In 1985, Alon and Tarsi conjectured that the length of a shortest cycle cover of a bridgeless graph H is at most 7/5 |E(H|). The conjecture is still open. Let G be a 2-edge-connected graph embedded with face-width k on the non-spherical orientable surface S_g. We give an upper bound on the length of a cycle cover of G. In particular, if g = 1 and k ≥ 48, or g = 2 and k ≥ 427, or g ≥ 3 and k ≥ 288(4^g - 1), then the upper bound is 7/5 |E(G|), which means that Alon and Tarsi’s conjecture holds for such a graph.     

Equalities on the number of conjugacy classes of the Sylow p-subgroups of GL(n,q)

We denote by Gn the group of the upper unitriangular matrices over F_q, the finite field with q = p^t elements, and r(G_n) the number of conjugacy classes of G_n. In this paper, we obtain the value of r(G_n) modulo (q² -1)(q -1). We prove the following equalities