An Upper Bound for the Total Domination Subdivision Number of a Graph

A set S of vertices of a graph G = (V, E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γ _t (G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number sd_gt(G){{\rm sd}_{\gamma_t}(G)} is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the total domination number. In this paper, we prove that sd_gt(G) ￡ 2g_t(G)-1{{\rm sd}_{\gamma_t}(G)\leq 2\gamma_t(G)-1} for every simple connected graph G of order n ≥ 3.     

On the Roman Bondage Number of Planar Graphs

A Roman dominating function on a graph G is a function f : V(G) → {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 a Roman dominating function is the value f (V(G)) = ?_{u ? V(G)} f (u){f (V(G)) = \sum_{u\in V(G)} f (u)}. The Roman domination number, γ _R (G), of G is the minimum weight of a Roman dominating function on G. The Roman bondage number b _R (G) of a graph G with maximum degree at least two is the minimum cardinality of all sets E^￠ í E(G){E^{\prime} \subseteq E(G)} for which γ _R (G − E′) > γ _R (G). In this paper we present different bounds on the Roman bondage number of planar graphs.     

Color Chain of a Graph

For a simple connected undirected graph G, c(G), c_f(G), Y_f(G), f(G), ?G(G){\chi(G), \chi_f(G), \Psi_f(G), \phi(G), \partial \Gamma (G)} and Ψ(G) denote respectively the chromatic number, fall chromatic number (assuming that it exists for G), fall achromatic number, b-chromatic number, partial Grundy number and achromatic number of G. It is shown in Dunbar et al. (J Combin Math & Combin Comput 33:257–273, 2000) that for any graph G for which fall coloring exists, c(G) ￡ c_f(G) ￡ Y_f (G) ￡ f(G) ￡ ?G(G) ￡ Y(G){\chi (G)\leq \chi_f(G) \leq \Psi_f (G) \leq \phi(G) \leq \partial \Gamma (G)\leq \Psi (G)} . In this paper, we exhibit an infinite family of graphs G with a strictly increasing color chain: c(G) < c_f(G) < Y_f (G) < f(G) < ?G(G) < Y(G){\chi (G) < \chi_f(G) < \Psi_f (G) < \phi(G) < \partial \Gamma (G) < \Psi (G)} . The existence of such a chain was raised by Dunbar et al.     

The Number of Independent Sets in a Graph with Small Maximum Degree

Let ind(G) be the number of independent sets in a graph G. We show that if G has maximum degree at most 5 then

Vertex-Distinguishing Edge Colorings of Graphs with Degree Sum Conditions

An edge coloring is called vertex-distinguishing if every two distinct vertices are incident to different sets of colored edges. The minimum number of colors required for a vertex-distinguishing proper edge coloring of a simple graph G is denoted by c￠_vd(G){\chi'_{vd}(G)}. It is proved that c￠_vd(G) ￡ D(G)+5{\chi'_{vd}(G)\leq\Delta(G)+5} if G is a connected graph of order n ≥ 3 and s₂(G) 3 \frac2n3{\sigma_{2}(G)\geq\frac{2n}{3}}, where σ ₂(G) denotes the minimum degree sum of two nonadjacent vertices in G.     

Roman Domination Dot-critical Graphs

A Roman dominating function on a graph G is a function f : V(G) → {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 a Roman dominating function is the value ${f(V(G))=\sum_{u \in V(G)}f(u)}$ . The Roman domination number, γ _R (G), of G is the minimum weight of a Roman dominating function on G. In this paper, we study graphs for which contracting any edge decreases the Roman domination number.     

A New Bound on the Total Domination Subdivision Number

A set S of vertices of a graph G = (V, E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γ _t (G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the total domination number. In this paper we prove that for every simple connected graph G of order n ≥ 3,

Disproof of a Conjecture on the Subdivision Domination Number of a Graph

A set S of vertices of a graph G = (V,E) is a dominating set if every vertex of is adjacent to some vertex in S. The domination number γ(G) is the minimum cardinality of a dominating set of G. The domination subdivision number sd_γ(G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the domination number. Haynes et al. (Discussiones Mathematicae Graph Theory 21 (2001) 239-253) conjectured that for any graph G with . In this note we first give a counterexample to this conjecture in general and then we prove it for a particular class of graphs.     

Connected Domination Number of a Graph and its Complement

A set S of vertices in a graph G is a connected dominating set if every vertex not in S is adjacent to some vertex in S and the subgraph induced by S is connected. The connected domination number γ _c (G) is the minimum size of such a set. Let d^*(G)=min{d(G),d([`(G)])}{\delta^*(G)={\rm min}\{\delta(G),\delta({\overline{G}})\}} , where [`(G)]{{\overline{G}}} is the complement of G and δ(G) is the minimum vertex degree. We prove that when G and [`(G)]{{\overline{G}}} are both connected, g<sub>c</sub>(G)+g<sub>c</sub>([`(G)]) ￡ d^*(G)+4-(g_c(G)-3)(g_c([`(G)])-3){{\gamma_c}(G)+{\gamma_c}({\overline{G}})\le \delta^*(G)+4-({\gamma_c}(G)-3)({\gamma_c}({\overline{G}})-3)} . As a corollary, g<sub>c</sub>(G)+g<sub>c</sub>([`(G)]) ￡ \frac3n4{{\gamma_c}(G)+{\gamma_c}({\overline{G}})\le \frac{3n}{4}} when δ*(G) ≥ 3 and n ≥ 14, where G has n vertices. We also prove that g_c(G)+g_c([`(G)]) ￡ d<sup>*</sup>(G)+2{{\gamma_c}(G)+{\gamma_c}({\overline{G}})\le \delta^*(G)+2} when g<sub>c</sub>(G),g<sub>c</sub>([`(G)]) 3 4{{\gamma_c}(G),{\gamma_c}({\overline{G}})\ge 4} . This bound is sharp when δ*(G) = 6, and equality can only hold when δ*(G) = 6. Finally, we prove that g_c(G)g_c([`(G)]) ￡ 2n-4{{\gamma_c}(G){\gamma_c}({\overline{G}})\le 2n-4} when n ≥ 7, with equality only for paths and cycles.     

Roman and Total Domination

Abstract

A set S of vertices is a total dominating set of a graph G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set is the total domination number ^γt(G). A Roman dominating function on a graph G is a function f : V (G) → {0, 1, 2} satisfying the condition that every vertex u with f (u)=0 is adjacent to at least one vertex v of G for which f (v)=2. The minimum of f (V (G))=∑_{u ∈ V (G)} f (u) over all such functions is called the Roman domination number γR (G). We show that γt(G) ≤ γR (G) with equality if and only if ^γt(G)=2γ(G), where γ(G) is the domination number of G. Moreover, we characterize the extremal graphs for some graph families.     

A note on Roman domination in graphs

Let G=(V,E) be a simple graph. A subset S⊆V is a dominating set of G, if for any vertex u∈V-S, there exists a vertex v∈S such that uv∈E. The domination number of G, γ(G), equals the minimum cardinality of a dominating set. A Roman dominating function on graph G=(V,E) is a function f:V→{0,1,2} satisfying the condition that every vertex v for which f(v)=0 is adjacent to at least one vertex u for which f(u)=2. The weight of a Roman dominating function is the value f(V)=∑_v∈Vf(v). The Roman domination number of a graph G, denoted by γ_R(G), equals the minimum weight of a Roman dominating function on G. In this paper, for any integer k(2?k?γ(G)), we give a characterization of graphs for which γ_R(G)=γ(G)+k, which settles an open problem in [E.J. Cockayne, P.M. Dreyer Jr, S.M. Hedetniemi et al. On Roman domination in graphs, Discrete Math. 278 (2004) 11-22].     

Upper Bounds on the Paired Domination Subdivision Number of a Graph

A paired dominating set of a graph G with no isolated vertex is a dominating set S of vertices such that the subgraph induced by S in G has a perfect matching. The paired domination number of G, denoted by γ _pr(G), is the minimum cardinality of a paired dominating set of G. The paired domination subdivision number ${{\rm sd}_{\gamma _{\rm pr}}(G)}$ is the minimum number of edges to be subdivided (each edge of G can be subdivided at most once) in order to increase the paired domination number. In this paper, we show that if G is a connected graph of order at least 4, then ${{\rm sd}_{\gamma _{\rm pr}}(G)\leq 2|V(G)|-5}$ . We also characterize trees T such that ${{\rm sd}_{\gamma _{\rm pr}}(T) \geq |V(T)| /2}$ .     

Unique response Roman domination in graphs

A function f:V(G)→{0,1,2} is a Roman dominating function if every vertex u for which f(u)=0 is adjacent to at least one vertex v for which f(v)=2. A function f:V(G)→{0,1,2} with the ordered partition (V₀,V₁,V₂) of V(G), where V_i={v∈V(G)∣f(v)=i} for i=0,1,2, is a unique response Roman function if x∈V₀ implies |N(x)∩V₂|≤1 and x∈V₁∪V₂ implies that |N(x)∩V₂|=0. A function f:V(G)→{0,1,2} is a unique response Roman dominating function if it is a unique response Roman function and a Roman dominating function. The unique response Roman domination number of G, denoted by u_R(G), is the minimum weight of a unique response Roman dominating function. In this paper we study the unique response Roman domination number of graphs and present bounds for this parameter.     

A new characterization for some linear groups

Let G be a group and π _e (G) be the set of element orders of G. Let k ? p_e(G){k\in\pi_e(G)} and m _k be the number of elements of order k in G. Let nse(G) = {m_k|k ? p_e(G)}{{\rm nse}(G) = \{m_k|k\in\pi_e(G)\}} . In Shen et al. (Monatsh Math, 2009), the authors proved that A₄ @ PSL(2, 3), A₅ @ PSL(2, 4) @ PSL(2,5){A_4\cong {\rm PSL}(2, 3), A_5\cong \rm{PSL}(2, 4)\cong \rm{PSL}(2,5)} and A₆ @ PSL(2,9){A_6\cong \rm{PSL}(2,9)} are uniquely determined by nse(G). In this paper, we prove that if G is a group such that nse(G) = nse(PSL(2, q)), where q ? {7,8,11,13}{q\in\{7,8,11,13\}} , then G @ PSL(2,q){G\cong {PSL}(2,q)} .     

An Introduction to Closed/Open Neighborhood Sums: Minimax, Maximin, and Spread

For a graph G of order |V(G)| = n and a real-valued mapping f:V(G)?\mathbbR{f:V(G)\rightarrow\mathbb{R}}, if S ì V(G){S\subset V(G)} then f(S)=?_{w ? S} f(w){f(S)=\sum_{w\in S} f(w)} is called the weight of S under f. The closed (respectively, open) neighborhood sum of f is the maximum weight of a closed (respectively, open) neighborhood under f, that is, NS[f]=max{f(N[v])|v ? V(G)}{NS[f]={\rm max}\{f(N[v])|v \in V(G)\}} and NS(f)=max{f(N(v))|v ? V(G)}{NS(f)={\rm max}\{f(N(v))|v \in V(G)\}}. The closed (respectively, open) lower neighborhood sum of f is the minimum weight of a closed (respectively, open) neighborhood under f, that is, NS^-[f]=min{f(N[v])|v ? V(G)}{NS^{-}[f]={\rm min}\{f(N[v])|v\in V(G)\}} and NS^-(f)=min{f(N(v))|v ? V(G)}{NS^{-}(f)={\rm min}\{f(N(v))|v\in V(G)\}}. For W ì \mathbbR{W\subset \mathbb{R}}, the closed and open neighborhood sum parameters are NS_W[G]=min{NS[f]|f:V(G)? W{NS_W[G]={\rm min}\{NS[f]|f:V(G)\rightarrow W} is a bijection} and NS_W(G)=min{NS(f)|f:V(G)? W{NS_W(G)={\rm min}\{NS(f)|f:V(G)\rightarrow W} is a bijection}. The lower neighbor sum parameters are NS^-_W[G]=maxNS^-[f]|f:V(G)? W{NS^{-}_W[G]={\rm max}NS^{-}[f]|f:V(G)\rightarrow W} is a bijection} and NS^-_W(G)=maxNS^-(f)|f:V(G)? W{NS^{-}_W(G)={\rm max}NS^{-}(f)|f:V(G)\rightarrow W} is a bijection}. For bijections f:V(G)? {1,2,?,n}{f:V(G)\rightarrow \{1,2,\ldots,n\}} we consider the parameters NS[G], NS(G), NS ⁻[G] and NS ⁻(G), as well as two parameters minimizing the maximum difference in neighborhood sums.     

All 4-Edge-Connected HHD-Free Graphs are {\mathbb{Z}_3}-Connected

An undirected graph G = (V, E) is called \mathbbZ₃{\mathbb{Z}_3}-connected if for all b: V ? \mathbbZ₃{b: V \rightarrow \mathbb{Z}_3} with ?_{v ? V}b(v)=0{\sum_{v \in V}b(v)=0}, an orientation D = (V, A) of G has a \mathbbZ₃{\mathbb{Z}_3}-valued nowhere-zero flow f: A? \mathbbZ₃-{0}{f: A\rightarrow \mathbb{Z}_3-\{0\}} such that ?_{e ? d⁺(v)}f(e)-?_{e ? d^-(v)}f(e)=b(v){\sum_{e \in \delta^+(v)}f(e)-\sum_{e \in \delta^-(v)}f(e)=b(v)} for all v ? V{v \in V}. We show that all 4-edge-connected HHD-free graphs are \mathbbZ₃{\mathbb{Z}_3}-connected. This extends the result due to Lai (Graphs Comb 16:165–176, 2000), which proves the \mathbbZ₃{\mathbb{Z}_3}-connectivity for 4-edge-connected chordal graphs.     

Simple exceptional groups of Lie type are determined by their character degrees

Let G be a finite group. Denote by Irr(G) the set of all irreducible complex characters of G. Let cd(G)={c(1)  |  c ? Irr(G)}{{\rm cd}(G)=\{\chi(1)\;|\;\chi\in {\rm Irr}(G)\}} be the set of all irreducible complex character degrees of G forgetting multiplicities, and let X₁(G) be the set of all irreducible complex character degrees of G counting multiplicities. Let H be any non-abelian simple exceptional group of Lie type. In this paper, we will show that if S is a non-abelian simple group and cd(S) í cd(H){{\rm cd}(S)\subseteq {\rm cd}(H)} then S must be isomorphic to H. As a consequence, we show that if G is a finite group with X₁(G) í X₁(H){{\rm X}_1(G)\subseteq {\rm X}_1(H)} then G is isomorphic to H. In particular, this implies that the simple exceptional groups of Lie type are uniquely determined by the structure of their complex group algebras.     

On Representations of Integers in Thin Subgroups of {{\rm SL}_2({\mathbb {Z}})}

Let ${\Gamma < {\rm SL}(2, {\mathbb Z})}Let G < SL(2, \mathbb Z){\Gamma < {\rm SL}(2, {\mathbb Z})} be a free, finitely generated Fuchsian group of the second kind with no parabolics, and fix two primitive vectors v₀, w₀ ? \mathbb Z²  \  {0}{v_{0}, w_{0} \in \mathbb {Z}^{2} \, {\backslash} \, \{0\}}. We consider the set S{\mathcal {S}} of all integers occurring in áv₀g, w₀?{\langle v_{0}\gamma, w_{0}\rangle}, for g ? G{\gamma \in \Gamma} and the usual inner product on \mathbb R²{\mathbb {R}^2}. Assume that the critical exponent δ of Γ exceeds 0.99995, so that Γ is thin but not too thin. Using a variant of the circle method, new bilinear forms estimates and Gamburd’s 5/6-th spectral gap in infinite-volume, we show that S{\mathcal {S}} contains almost all of its admissible primes, that is, those not excluded by local (congruence) obstructions. Moreover, we show that the exceptional set \mathfrak E(N){\mathfrak {E}(N)} of integers |n| < N which are locally admissible (n ? S   (mod  q)   for all   q 3 1){(n \in \mathcal {S} \, \, ({\rm mod} \, q) \, \, {\rm for\,all} \,\, q \geq 1)} but fail to be globally represented, n ? S{n \notin \mathcal {S}}, has a power savings, |\mathfrak E(N)| << N^1-e₀{|\mathfrak {E}(N)| \ll N^{1-\varepsilon_{0}}} for some ${\varepsilon_{0} > 0}${\varepsilon_{0} > 0}, as N → ∞.     

Global classical solutions for reaction–diffusion systems with nonlinearities of exponential growth

The aim of this study is to prove global existence of classical solutions for systems of the form ${\frac{\partial u}{\partial t} -a \Delta u=-f(u,v)}The aim of this study is to prove global existence of classical solutions for systems of the form \frac?u?t -a Du=-f(u,v){\frac{\partial u}{\partial t} -a \Delta u=-f(u,v)} , \frac?v?t -b Dv=g(u,v){\frac{\partial v}{\partial t} -b \Delta v=g(u,v)} in (0, +∞) × Ω where Ω is an open bounded domain of class C ¹ in \mathbbRⁿ{\mathbb{R}^n}, a > 0, b > 0 and f, g are nonnegative continuously differentiable functions on [0, +∞) × [0, +∞) satisfying f (0, η) = 0, g(x,h) ￡ C j(x)e^ahb{g(\xi,\eta) \leq C \varphi(\xi)e^{\alpha {\eta^\beta}}} and g(ξ, η) ≤ ψ(η)f(ξ, η) for some constants C > 0, α > 0 and β ≥ 1 where j{\varphi} and ψ are any nonnegative continuously differentiable functions on [0, +∞) such that j(0)=0{\varphi(0)=0} and lim_{h? +￥}h^b-1y(h) = l{ \lim_{\eta \rightarrow +\infty}\eta^{\beta -1}\psi(\eta)= \ell} where ℓ is a nonnegative constant. The asymptotic behavior of the global solutions as t goes to +∞ is also studied. For this purpose, we use the appropriate techniques which are based on semigroups, energy estimates and Lyapunov functional methods.     

Probability measures on [SIN] groups and some related ideals in group algebras

Given a locally compact group G, let J(G){\cal J}(G) denote the set of closed left ideals in L ¹(G), of the form J _μ = [L¹(G) * (δ _e − μ)]⁻, where μ is a probability measure on G. Let J_d(G)={\cal J}_d(G)= {J_m;m is discrete}\{J_{\mu};\mu\ {\rm is discrete}\} , J_a(G)={J_m;m is absolutely continuous}{\cal J}_a(G)=\{J_{\mu};\mu\ {\rm is absolutely continuous}\} . When G is a second countable [SIN] group, we prove that J(G)=J_d(G){\cal J}(G)={\cal J}_d(G) and that J_a(G){\cal J}_a(G) , being a proper subset of J(G){\cal J}(G) when G is nondiscrete, contains every maximal element of J(G){\cal J}(G) . Some results concerning the ideals J _μ in general locally compact second countable groups are also obtained.