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.     

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

An Erd?s-Gallai Theorem for Matroids

Erdős and Gallai showed that for any simple graph with n vertices and circumference c it holds that | E(G) | ￡ \frac12(n - 1)c{{{\mid}{E(G)}{\mid} \leq {\frac{1}{2}}(n - 1)c}}. We extend this theorem to simple binary matroids having no F ₇-minor by showing that for such a matroid M with circumference c(M) ≥  3 it holds that | E(M) | ￡ \frac12r(M)c(M){{{\mid}{E(M)}{\mid} \leq {\frac{1}{2}}r(M)c(M)}}.     

Proof of a conjecture of V. Nikiforov

Using analytical tools, we prove that for any simple graph G on n vertices and its complement [`(G)]\bar G the inequality $\mu \left( G \right) + \mu \left( {\bar G} \right) \leqslant \tfrac{4} {3}n - 1$\mu \left( G \right) + \mu \left( {\bar G} \right) \leqslant \tfrac{4} {3}n - 1 holds, where μ(G) and m( [`(G)] )\mu \left( {\bar G} \right) denote the greatest eigenvalue of adjacency matrix of the graphs G and [`(G)]\bar G respectively.     

Nonoscillation theorems for certain second order nonlinear differential equations

Some necessary and sufficient conditions for nonoscillation are established for the second order nonlinear differential equation (r(t)y(x(t))|x^￠(t)|^p-1x^￠(t))^￠+c(t)f(x(t))=0,    t 3 t₀,(r(t)\psi(x(t))\vert x^{\prime}(t)\vert^{p-1}x^{\prime}(t))^{\prime}+c(t)f(x(t))=0,\quad t\ge t_0,     

Arithmetic mean of differences of Dedekind sums

Recently, Girstmair and Schoissengeier studied the asymptotic behavior of the arithmetic mean of Dedekind sums \frac1j(N) ? _{0 ￡ m < Ngcd(m,N)=1} |S(m,N)|\frac{1}{\varphi(N)} \sum_{\mathop{\mathop{ 0 \le m< N}}\limits_{\gcd(m,N)=1}} \vert S(m,N)\vert , as N → ∞. In this paper we consider the arithmetic mean of weighted differences of Dedekind sums in the form A_h(Q)=\frac1?_{\fracaq ? FQ}h(\fracaq) ×?_{\fracaq ? FQ}h(\fracaq) |s(a^￠,q^￠)-s(a,q)|A_{h}(Q)=\frac{1}{\sum_{\frac{a}{q} \in {\cal F}_{Q}}h\left(\frac{a}{q}\right)} \times \sum_{\frac{a}{q} \in {\cal F}_{\!Q}}h\left(\frac{a}{q}\right) \vert s(a^{\prime},q^{\prime})-s(a,q)\vert , where h:[0,1] ? \Bbb Ch:[0,1] \rightarrow {\Bbb C} is a continuous function with ò₀¹ h(t)  d t 1 0\int_0^1 h(t) \, {\rm d} t \ne 0 , \fracaq{\frac{a}{q}} runs over F_Q{\cal F}_{\!Q} , the set of Farey fractions of order Q in the unit interval [0,1] and \fracaq < \fraca^￠q^￠{\frac{a}{q}}<\frac{a^{\prime}}{q^{\prime}} are consecutive elements of F_Q{\cal F}_{\!Q} . We show that the limit lim _Q→∞ A _h (Q) exists and is independent of h.     

Pan-H-Linked Graphs

Let H be a multigraph, possibly containing loops. An H-subdivision is any simple graph obtained by replacing the edges of H with paths of arbitrary length. Let H be an arbitrary multigraph of order k, size m, n ₀(H) isolated vertices and n ₁(H) vertices of degree one. In Gould and Whalen (Graphs Comb. 23:165–182, 2007) it was shown that if G is a simple graph of order n containing an H-subdivision H{\mathcal{H}} and d(G) 3 \fracn+m-k+n₁(H)+2n₀(H)2{\delta(G) \ge \frac{n+m-k+n_1(H)+2n_0(H)}{2}}, then G contains a spanning H-subdivision with the same ground set as H{\mathcal{H}} . As a corollary to this result, the authors were able to obtain Dirac’s famed theorem on hamiltonian graphs; namely that if G is a graph of order n ≥ 3 with d(G) 3 \fracn2{\delta(G)\ge\frac{n}{2}} , then G is hamiltonian. Bondy (J. Comb. Theory Ser. B 11:80–84, 1971) extended Dirac’s theorem by showing that if G satisfied the condition d(G) 3 \fracn2{\delta(G) \ge \frac{n}{2}} then G was either pancyclic or a complete bipartite graph. In this paper, we extend the result from Gould and Whalen (Graphs Comb. 23:165–182, 2007) in a similar manner. An H-subdivision H{\mathcal{H}} in G is 1-extendible if there exists an H-subdivision H^*{\mathcal{H}^{*}} with the same ground set as H{\mathcal{H}} and |H^*| = |H| + 1{|\mathcal{H}^{*}| = |\mathcal{H}| + 1} . If every H-subdivision in G is 1-extendible, then G is pan-H-linked. We demonstrate that if H is sufficiently dense and G is a graph of large enough order n such that d(G) 3 \fracn+m-k+n₁(H)+2n₀(H)2{\delta(G) \ge \frac{n+m-k+n_1(H)+2n_0(H)}{2}} , then G is pan-H-linked. This result is sharp.     

Characterization and the pre-Schwarzian norm estimate for concave univalent functions

Let Co(α) denote the class of concave univalent functions in the unit disk \mathbbD{\mathbb{D}}. Each function f ? Co(a){f\in Co(\alpha)} maps the unit disk \mathbbD{\mathbb{D}} onto the complement of an unbounded convex set. In this paper we find the exact disk of variability for the functional (1-|z|²)( f^￠￠(z)/f^￠(z)), f ? Co(a){(1-|z|^2)\left ( f^{\prime\prime}(z)/f^{\prime}(z)\right), f\in Co(\alpha)}. In particular, this gives sharp upper and lower estimates for the pre-Schwarzian norm of concave univalent functions. Next we obtain the set of variability of the functional (1-|z|²)(f^￠￠(z)/f^￠(z)), f ? Co(a){(1-|z|^2)\left(f^{\prime\prime}(z)/f^{\prime}(z)\right), f\in Co(\alpha)} whenever f′′(0) is fixed. We also give a characterization for concave functions in terms of Hadamard convolution. In addition to sharp coefficient inequalities, we prove that functions in Co(α) belong to the H ^p space for p < 1/α.     

Univalent Functions, <Emphasis Type="Italic">VMOA</Emphasis> and Related Spaces

This paper is concerned mainly with the logarithmic Bloch space ℬ_log which consists of those functions f which are analytic in the unit disc \mathbbD{\mathbb{D}} and satisfy sup_{|z| < 1}(1-|z|)log\frac11-|z||f^￠(z)| < ￥\sup_{\vert z\vert <1}(1-\vert z\vert )\log\frac{1}{1-\vert z\vert}\vert f^{\prime}(z)\vert <\infty , and the analytic Besov spaces B ^p , 1≤p<∞. They are all subspaces of the space VMOA. We study the relation between these spaces, paying special attention to the membership of univalent functions in them. We give explicit examples of:

The Cycle Discrepancy of Three-Regular Graphs

Let G = (V, E) be an undirected graph and C(G){{\mathcal C}(G)} denote the set of all cycles in G. We introduce a graph invariant cycle discrepancy, which we define as

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.     

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)} .     

Constructing a spanning tree with many leaves

It was shown by Griggs and Wu that a graph of minimal degree 4 on n vertices has a spanning tree with at least \frac25 \frac{2}{5} n leaves, which is asymptomatically the best possible bound for this class of graphs. In this paper, we present a polynomial time algorithm that finds in any graph with k vertices of degree greater than or equal to 4 and k′ vertices of degree 3 a spanning tree with [ \frac25 ·k + \frac215 ·k￠ ] \left[ {\frac{2}{5} \cdot k + \frac{2}{{15}} \cdot k'} \right] leaves.     

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.     

Micro-Local Analysis with Fourier Lebesgue Spaces. Part?I

Let ω,ω ₀ be appropriate weight functions and q∈[1,∞]. We introduce the wave-front set, WF_FL^q(w)(f)\mathrm{WF}_{\mathcal{F}L^{q}_{(\omega)}}(f) of f ? S￠f\in \mathcal{S}' with respect to weighted Fourier Lebesgue space FL^q_(w)\mathcal{F}L^{q}_{(\omega )}. We prove that usual mapping properties for pseudo-differential operators Op (a) with symbols a in S^(w₀)_r,0S^{(\omega _{0})}_{\rho ,0} hold for such wave-front sets. Especially we prove that

Boxicity of Circular Arc Graphs

A k-dimensional box is a Cartesian product R ₁ × · · · × R _k where each R _i is a closed interval on the real line. The boxicity of a graph G, denoted as box(G), is the minimum integer k such that G can be represented as the intersection graph of a collection of k-dimensional boxes. That is, two vertices are adjacent if and only if their corresponding boxes intersect. A circular arc graph is a graph that can be represented as the intersection graph of arcs on a circle. We show that if G is a circular arc graph which admits a circular arc representation in which no arc has length at least p(\fraca-1a){\pi(\frac{\alpha-1}{\alpha})} for some a ? \mathbbN _{3 2}{\alpha\in\mathbb{N}_{\geq 2}}, then box(G) ≤ α (Here the arcs are considered with respect to a unit circle). From this result we show that if G has maximum degree D < ?\fracn(a-1)2a?{\Delta < \lfloor{\frac{n(\alpha-1)}{2\alpha}}\rfloor} for some a ? \mathbbN _{3 2}{\alpha \in \mathbb{N}_{\geq 2}}, then box(G) ≤ α. We also demonstrate a graph having box(G) > α but with D = n\frac(a-1)2a+ \fracn2a(a+1)+(a+2){\Delta=n\frac{(\alpha-1)}{2\alpha}+ \frac{n}{2\alpha(\alpha+1)}+(\alpha+2)}. For a proper circular arc graph G, we show that if D < ?\fracn(a-1)a?{\Delta < \lfloor{\frac{n(\alpha-1)}{\alpha}}\rfloor} for some a ? \mathbbN _{3 2}{\alpha\in \mathbb{N}_{\geq 2}}, then box(G) ≤ α. Let r be the cardinality of the minimum overlap set, i.e. the minimum number of arcs passing through any point on the circle, with respect to some circular arc representation of G. We show that for any circular arc graph G, box(G) ≤ r + 1 and this bound is tight. We show that if G admits a circular arc representation in which no family of k ≤ 3 arcs covers the circle, then box(G) ≤ 3 and if G admits a circular arc representation in which no family of k ≤ 4 arcs covers the circle, then box(G) ≤ 2. We also show that both these bounds are tight.     

Periodic Positive Solution to a Class of Singular Second-Order Ordinary Differential Equations

This paper studies the existence of a positive solution to the second-order periodic boundary value problem

Fractional f-Edge Cover Chromatic Index of Graphs

Let G be a graph, and let f be an integer function on V with ${1\leq f(v)\leq d(v)}$ to each vertex ${\upsilon \in V}$ . An f-edge cover coloring is a coloring of edges of E(G) such that each color appears at each vertex ${\upsilon \in V(G)}$ at least f(υ) times. The maximum number of colors needed to f-edge cover color G is called the f-edge cover chromatic index of G and denoted by ${\chi^{'}_{fc}(G)}$ . It is well known that any simple graph G has the f-edge cover chromatic index equal to δ _f (G) or δ _f (G) ? 1, where ${\delta_{f}(G)=\,min\{\lfloor \frac{d(v)}{f(v)} \rfloor: v\in V(G)\}}$ . The fractional f-edge cover chromatic index of a graph G, denoted by ${\chi^{'}_{fcf}(G)}$ , is the fractional f-matching number of the edge f-edge cover hypergraph ${\mathcal{H}}$ of G whose vertices are the edges of G and whose hyperedges are the f-edge covers of G. In this paper, we give an exact formula of ${\chi^{'}_{fcf}(G)}$ for any graph G, that is, ${\chi^{'}_{fcf}(G)=\,min \{\min\limits_{v\in V(G)}d_{f}(v), \lambda_{f}(G)\}}$ , where ${\lambda_{f}(G)=\min\limits_{S} \frac{|C[S]|}{\lceil (\sum\limits_{v\in S}{f(v)})/2 \rceil}}$ and the minimum is taken over all nonempty subsets S of V(G) and C[S] is the set of edges that have at least one end in S.     

Roman domination subdivision number of graphs

A Roman dominating function on a graph G = (V, E) is a function f : V ? {0, 1, 2}f : V \rightarrow \{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 w(f) = ?_{v ? V} f(v)w(f) = \sum_{v\in V} f(v). The Roman domination number of a graph G, denoted by _gR(G)_{\gamma R}(G), equals the minimum weight of a Roman dominating function on G. The Roman domination subdivision number sd_gR(G)sd_{\gamma R}(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 Roman domination number. In this paper, first we establish upper bounds on the Roman domination subdivision number for arbitrary graphs in terms of vertex degree. Then we present several different conditions on G which are sufficient to imply that $1 \leq sd_{\gamma R}(G) \leq 3$1 \leq sd_{\gamma R}(G) \leq 3. Finally, we show that the Roman domination subdivision number of a graph can be arbitrarily large.