Nordhaus-Gaddum results for the sum of the induced path number of a graph and its complement

The induced path number ρ(G) of a graph G is defined as the minimum number of subsets into which the vertex set of G can be partitioned so that each subset induces a path.Broere et al.proved that if G is a graph of order n,then n~(1/2) ≤ρ(G) + ρ(■) ≤ [3n/2].In this paper,we characterize the graphs G for which ρ(G) + ρ(■) = [3n/2],improve the lower bound on ρ(G) + ρ(■) by one when n is the square of an odd integer,and determine a best possible upper bound for ρ(G) + ρ(■) when neither G nor ■ has isolated vertices.     

Collapsible Graphs and Hamiltonicity of Line Graphs

Thomassen conjectured that every 4-connected line graph is Hamiltonian. Chen and Lai (Combinatorics and Graph Theory, vol 95, World Scientific, Singapore, pp 53–69; Conjecture 8.6 of 1995) conjectured that every 3-edge connected and essentially 6-edge connected graph is collapsible. Denote D ₃(G) the set of vertices of degree 3 of graph G. For ${e = uv \in E(G)}$ , define d(e) = d(u) + d(v) ? 2 the edge degree of e, and ${\xi(G) = \min\{d(e) : e \in E(G)\}}$ . Denote by λ ^m (G) the m-restricted edge-connectivity of G. In this paper, we prove that a 3-edge-connected graph with ${\xi(G)\geq7}$ , and ${\lambda^3(G)\geq7}$ is collapsible; a 3-edge-connected simple graph with ${\xi(G)\geq7}$ , and ${\lambda^3(G)\geq6}$ is collapsible; a 3-edge-connected graph with ${\xi(G)\geq6}$ , ${\lambda^2(G)\geq4}$ , and ${\lambda^3(G)\geq6}$ with at most 24 vertices of degree 3 is collapsible; a 3-edge-connected simple graph with ${\xi(G)\geq6}$ , and ${\lambda^3(G)\geq5}$ with at most 24 vertices of degree 3 is collapsible; a 3-edge-connected graph with ${\xi(G)\geq5}$ , and ${\lambda^2(G)\geq4}$ with at most 9 vertices of degree 3 is collapsible. As a corollary, we show that a 4-connected line graph L(G) with minimum degree at least 5 and ${|D_3(G)|\leq9}$ is Hamiltonian.     

Cops and Robber Game with a Fast Robber on Expander Graphs and Random Graphs

We consider a variant of the Cops and Robber game, in which the robber has unbounded speed, i.e., can take any path from her vertex in her turn, but she is not allowed to pass through a vertex occupied by a cop. Let ${c_{\infty}(G)}$ denote the number of cops needed to capture the robber in a graph G in this variant. We characterize graphs G with c _??(G) =? 1, and give an ${O( \mid V(G)\mid^2)}$ algorithm for their detection. We prove a lower bound for c _?? of expander graphs, and use it to prove three things. The first is that if ${np \geq 4.2 {\rm log}n}$ then the random graph ${G= \mathcal{G}(n, p)}$ asymptotically almost surely has ${\eta_{1}/p \leq \eta_{2}{\rm log}(np)/p}$ , for suitable positive constants ${\eta_{1}}$ and ${\eta_{2}}$ . The second is that a fixed-degree random regular graph G with n vertices asymptotically almost surely has ${c_{\infty}(G) = \Theta(n)}$ . The third is that if G is a Cartesian product of m paths, then ${n/4km^2 \leq c_{\infty}(G) \leq n/k}$ , where ${n = \mid V(G)\mid}$ and k is the number of vertices of the longest path.     

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.     

An Upper Bound for the Total Restrained Domination Number of Graphs

Let G be a graph with vertex set V. A set ${D \subseteq V}$ is a total restrained dominating set of G if every vertex in V has a neighbor in D and every vertex in ${V \setminus D}$ has a neighbor in ${V \setminus D}$ . The minimum cardinality of a total restrained dominating set of G is called the total restrained domination number of G, and is denoted by γ _tr (G). In this paper, we prove that if G is a connected graph of order n ≥ 4 and minimum degree at least two, then ${\gamma_{tr}(G) \leq n-\sqrt[3]{n \over 4}}$ .     

A relationship between bounds on the sum of squares of degrees of a graph

LetG = (V, E) be a simple graph withn vertices and e edges. Letdi be the degree of the ith vertex v_i ∈ V andm _i the average of the degrees of the vertices adjacent to vertexv _i ∈ V. It is known by Caen [1] and Das [2] that $\frac{{4e^2 }}{n} \leqslant d_1^2 + ... + d_n^2 \leqslant e max \{ d_j + m_j |v_j \in V\} \leqslant e\left( {\frac{{2e}}{{n - 1}} + n - 2} \right)$ . In general, the equalities do not hold in above inequality. It is shown that a graphG is regular if and only if $\frac{{4e^2 }}{n} = d_1^2 + ... + d_n^2 $ . In fact, it is shown a little bit more strong result that a graphG is regular if and only if $\frac{{4e^2 }}{n} = d_1^2 + ... + d_n^2 = e max \{ d_j + m_j |v_j \in V\} $ . For a graphG withn < 2 vertices, it is shown that G is a complete graphK _n if and only if $\frac{{4e^2 }}{n} = d_1^2 + ... + d_n^2 = e max \{ d_j + m_j |v_j \in V\} = e\left( {\frac{{2e}}{{n - 1}} + n - 2} \right)$ .     

On the average number of direct factors of a finite Abelian group

Let \(T(x) = \sum\limits_{ord(G) \leqq x} {t(G),} \) , wheret(G) define the number of direct factors of a finite Abelian group.E. Krätzel ([5]) defined a remainderΔ ₁(x) in the asymptotic ofT(x) and proved $$\Delta _1 (x)<< x^{{5 \mathord{\left/ {\vphantom {5 {12}}} \right. \kern-\nulldelimiterspace} {12}}} \log ^4 x.$$ Using two different methods to estimate a special three-dimensional exponential sum we get the better results $$\Delta _1 (x)<< x^{{{282} \mathord{\left/ {\vphantom {{282} {683}}} \right. \kern-\nulldelimiterspace} {683}}} \log ^4 x$$ and $$\Delta _1 (x)<< x^{{{45} \mathord{\left/ {\vphantom {{45} {109}}} \right. \kern-\nulldelimiterspace} {109}} + \varepsilon } (\varepsilon > 0).$$      

Note on Group Distance Magic Graphs G[C 4]

A group distance magic labeling or a ${\mathcal{G}}$ -distance magic labeling of a graph G =  (V, E) with ${|V | = n}$ is a bijection f from V to an Abelian group ${\mathcal{G}}$ of order n such that the weight ${w(x) = \sum_{y\in N_G(x)}f(y)}$ of every vertex ${x \in V}$ is equal to the same element ${\mu \in \mathcal{G}}$ , called the magic constant. In this paper we will show that if G is a graph of order n =  2 ^p (2k + 1) for some natural numbers p, k such that ${\deg(v)\equiv c \mod {2^{p+1}}}$ for some constant c for any ${v \in V(G)}$ , then there exists a ${\mathcal{G}}$ -distance magic labeling for any Abelian group ${\mathcal{G}}$ of order 4n for the composition G[C ₄]. Moreover we prove that if ${\mathcal{G}}$ is an arbitrary Abelian group of order 4n such that ${\mathcal{G} \cong \mathbb{Z}_2 \times\mathbb{Z}_2 \times \mathcal{A}}$ for some Abelian group ${\mathcal{A}}$ of order n, then there exists a ${\mathcal{G}}$ -distance magic labeling for any graph G[C ₄], where G is a graph of order n and n is an arbitrary natural number.     

A generalized Cole-Hopf transformation for a two-dimensional burgers equation with a variable coefficient

The direct method is applied to the two dimensional Burgers equation with a variable coefficient (u _t + uu _x ? u _xx ) _x + s(t)u _yy = 0 is transformed into the Riccati equation $H' - \tfrac{1} {2}H^2 + \left( {\tfrac{\rho } {2} - 1} \right)H = 0$ via the ansatz $u\left( {x,y,t} \right) = \tfrac{1} {{\sqrt t }}H(\rho ) + \tfrac{y} {{2\sqrt t }}\rho \left( {x,y,t} \right) = \tfrac{x} {{\sqrt t }} - y$ , provided that s(t) = t ^?3/2. Further, a generalized Cole-Hopf transformations $u\left( {x,y,t} \right) = \tfrac{y} {{2\sqrt t }} - \tfrac{2} {{\sqrt t }}\tfrac{{U_\rho (\rho ,r)}} {{U(\rho ,r)}}$ , $\rho \left( {x,y,t} \right) = \tfrac{x} {{\sqrt t }} - y$ , r(t) = log t is derived to linearize (u _t + uu _x ? u _xx ) _x + t ^?3/2 u _yy to the parabolic equation $U_r = U_{\rho \rho } + \left( {\tfrac{\rho } {2} - 1} \right)U_\rho$ .     

New upper bounds on linear coloring of planar graphs

A proper vertex coloring of a graph G is linear if the graph induced by the vertices of any two color classes is the union of vertex-disjoint paths. The linear chromatic number lc(G) of the graph G is the smallest number of colors in a linear coloring of G. In this paper, it is proved that every planar graph G with girth g and maximum degree Δ has(1)lc(G) ≤Δ 21 if Δ≥ 9; (2)lc(G) ≤「Δ/2」 + 7 ifg ≥ 5; (3) lc(G) ≤「Δ/2」 + 2 ifg ≥ 7 and Δ≥ 7.     

Graphs with Average Degree Smaller Than {\frac {30}{11}} Burn Slowly

In this paper, we consider the following firefighter problem on a finite graph G =  (V, E). Suppose that a fire breaks out at a given vertex ${v \in V}$ . In each subsequent time unit, a firefighter protects one vertex which is not yet on fire, and then the fire spreads to all unprotected neighbours of the vertices on fire. The objective of the firefighter is to save as many vertices as possible. The surviving rate ${\rho(G)}$ of G is defined as the expected percentage of vertices that can be saved when a fire breaks out at a random vertex of G. Let ε >  0. We show that any graph G on n vertices with at most ${(\frac {15}{11} - \varepsilon)n}$ edges can be well protected, that is, ${\rho(G) > \frac {\varepsilon}{60} > 0}$ . Moreover, a construction of a random graph is proposed to show that the constant ${\frac {15}{11}}$ cannot be improved.     

Degree Sum Conditions for Hamiltonicity on k-Partite Graphs

One of the earliest results about hamiltonian graphs was given by Dirac. He showed that if a graph G has order p and minimum degree at least \(\frac{p} {2}\) then G is hamiltonian. Moon and Moser showed that if G is a balanced bipartite graph (the two partite sets have the same order) with minimum degree more than \(\frac{p} {4}\) then G is hamiltonian. Recently their idea is generalized to k-partite graphs by Chen, Faudree, Gould, Jacobson, and Lesniak in terms of minimum degrees. In this paper, we generalize this result in terms of degree sum and the following result is obtained: Let G be a balanced k-partite graph with order kn. If for every pair of nonadjacent vertices u and v which are in different parts $$d(u) + d(v) > \left\{ {\begin{array}{*{20}c} {\left( {k - \frac{2} {{k + 1}}} \right)n} & {if k is odd} \\ {\left( {k - \frac{4} {{k + 2}}} \right)n} & {if k is even} \\ \end{array} } \right.,$$ then G is hamiltonian.     

On the Broadcast Independence Number of Grid Graph

A broadcast on a nontrivial connected graph G is a function ${f:V \longrightarrow \{0, \ldots,\operatorname{diam}(G)\}}$ such that for every vertex ${v \in V(G)}$ , ${f(v) \leq e(v)}$ , where ${\operatorname{diam}(G)}$ denotes the diameter of G and e(v) denotes the eccentricity of vertex v. The broadcast independence number is the maximum value of ${\sum_{v \in V} f(v)}$ over all broadcasts f that satisfy ${d(u,v) > \max \{f(u), f(v)\}}$ for every pair of distinct vertices u, v with positive values. We determine this invariant for grid graphs ${G_{m,n} = P_m \square P_n}$ , where ${2 \leq m \leq n}$ and □ denotes the Cartesian product. We hereby answer one of the open problems raised by Dunbar et al. in (Discrete Appl Math 154:59–75, 2006).     

On topological diversity of rectilinear representations of countably infinite graphs

We prove that, for each simple graph G whose set of vertices is countably infinite, there is a family ${\varvec{\mathcal{R}}(\varvec{G})}$ of the cardinality of the continuum of graphs such that (1) each graph ${\varvec{H} \in \varvec{\mathcal{R}}(\varvec{G})}$ is isomorphic to G, all vertices of H are points of the Euclidean space E ³, all edges of H are straight line segments (the ends of each edge are the vertices joined by it), the intersection of any two edges of H is either their common vertex or empty, and any isolated vertex of H does not belong to any edge of H; (2) all sets ${\varvec{\mathcal{B}}(\varvec{H})}$ ( ${\varvec{H} \in \varvec{\mathcal{R}}(\varvec{G})}$ ), where ${\varvec{\mathcal{B}}(\varvec{H})\subset \mathbf{E}^3}$ is the union of all vertices and all edges of H, are pairwise not homeomorphic; moreover, for any graphs ${\varvec{H}_1 \in \varvec{\mathcal{R}}(\varvec{G})}$ and ${\varvec{H}_2 \in \varvec{\mathcal{R}}(\varvec{G})}$ , ${\varvec{H}_1 \ne \varvec{H}_2}$ , and for any finite subsets ${\varvec{S}_i \subset \varvec{\mathcal{B}}(\varvec{H}_i)}$ (i = 1, 2), the sets ${\varvec{\mathcal{B}}(\varvec{H}_1){\setminus} \varvec{S}_1}$ and ${\varvec{\mathcal{B}}(\varvec{H}_2){\setminus} \varvec{S}_2}$ are not homeomorphic.     

On the Lucky Choice Number of Graphs

Suppose that G is a graph and ${f: V (G) \rightarrow \mathbb{N}}$ is a labeling of the vertices of G. Let S(v) denote the sum of labels over all neighbors of the vertex v in G. A labeling f of G is called lucky if ${S(u) \neq S(v),}$ for every pair of adjacent vertices u and v. Also, for each vertex ${v \in V(G),}$ let L(v) denote a list of natural numbers available at v. A list lucky labeling, is a lucky labeling f such that ${f(v) \in L(v),}$ for each ${v \in V(G).}$ A graph G is said to be lucky k-choosable if every k-list assignment of natural numbers to the vertices of G permits a list lucky labeling of G. The lucky choice number of G, η _l (G), is the minimum natural number k such that G is lucky k-choosable. In this paper, we prove that for every graph G with ${\Delta \geq 2, \eta_{l}(G) \leq \Delta^2-\Delta + 1,}$ where Δ denotes the maximum degree of G. Among other results we show that for every 3-list assignment to the vertices of a forest, there is a list lucky labeling which is a proper vertex coloring too.     

On the asymptotic behaviour of the ideal counting function in quadratic number fields

LetK be a quadratic number field with discriminantD and denote byF(n) the number of integral ideals with norm equal ton. Forr≥1 the following formula is proved $$\sum\limits_{n \leqslant x} {F(n)F(n + r) = M_K (r)x + E_K (x,r).} $$ HereM _k (r) is an explicitly determined function ofr which depends onK, and for every ε>0 the error term is bounded by \(|E_K (x,r)|<< |D|^{{3 \mathord{\left/ {\vphantom {3 2}} \right. \kern-0em} 2} + \varepsilon } x^{{5 \mathord{\left/ {\vphantom {5 6}} \right. \kern-0em} 6} + \varepsilon } \) uniformly for \(r<< |D|^{{1 \mathord{\left/ {\vphantom {1 2}} \right. \kern-0em} 2}} x^{{5 \mathord{\left/ {\vphantom {5 6}} \right. \kern-0em} 6}} \) Moreover,E _k (x,r) is small on average, i.e \(\int_X^{2X} {|E_K (x,r)|^2 dx}<< |D|^{4 + \varepsilon } X^{{5 \mathord{\left/ {\vphantom {5 2}} \right. \kern-0em} 2} + \varepsilon } \) uniformly for \(r<< |D|X^{{3 \mathord{\left/ {\vphantom {3 4}} \right. \kern-0em} 4}} \) .     

On oscillatory integral Hilbert transformation with trigonometric polynomial phase

Let $ \mathcal{P}_n $ denote the set of algebraic polynomials of degree n with the real coefficients. Stein and Wpainger [1] proved that $$ \mathop {\sup }\limits_{p( \cdot ) \in \mathcal{P}_n } \left| {p.v.\int_\mathbb{R} {\frac{{e^{ip(x)} }} {x}dx} } \right| \leqslant C_n , $$ where C _n depends only on n. Later A. Carbery, S. Wainger and J. Wright (according to a communication obtained from I. R. Parissis), and Parissis [3] obtained the following sharp order estimate $$ \mathop {\sup }\limits_{p( \cdot ) \in \mathcal{P}_n } \left| {p.v.\int_\mathbb{R} {\frac{{e^{ip(x)} }} {x}dx} } \right| \sim \ln n. $$ . Now let $ \mathcal{T}_n $ denote the set of trigonometric polynomials $$ t(x) = \frac{{a_0 }} {2} + \sum\limits_{k = 1}^n {(a_k coskx + b_k sinkx)} $$ with real coefficients a _k , b _k . The main result of the paper is that $$ \mathop {\sup }\limits_{t( \cdot ) \in \mathcal{T}_n } \left| {p.v.\int_\mathbb{R} {\frac{{e^{it(x)} }} {x}dx} } \right| \leqslant C_n , $$ with an effective bound on C _n . Besides, an analog of a lemma, due to I. M. Vinogradov, is established, concerning the estimate of the measure of the set, where a polynomial is small, via the coefficients of the polynomial.     

On the Edge Connectivity of Direct Products with Dense Graphs

Let ${\kappa^{\prime}(G)}$ be the edge connectivity of G and G × H the direct product of G and H. Let H be any graph with minimal degree ${\delta(H)>|V(H)|/2}$ . We prove that for any graph ${G, \kappa^{\prime}(G\times H)=\textup{min}\{2\kappa^{\prime}(G)|E(H)|,\delta(G)\delta(H)\}}$ . In addition, the structure of minimum edge cuts is described. As an application, we present a necessary and sufficient condition for G × K _n (n ≥ 3) to be super edge connected.     

Domination in Bipartite Graphs and in Their Complements

The domatic numbers of a graph G and of its complement $\bar G$ were studied by J. E. Dunbar, T. W. Haynes and M. A. Henning. They suggested four open problems. We will solve the following ones: Characterize bipartite graphs G having $d\left( G \right) = d\left( {\bar G} \right)$ Further, we will present a partial solution to the problem: Is it true that if G is a graph satisfying $d\left( G \right) = d\left( {\bar G} \right)$ then $\gamma \left( G \right) = \gamma \left( {\bar G} \right)$ ? Finally, we prove an existence theorem concerning the total domatic number of a graph and of its complement     

On the second eigenvalue and random walks in randomd-regular graphs

The main goal of this paper is to estimate the magnitude of the second largest eigenvalue in absolute value, λ₂, of (the adjacency matrix of) a randomd-regular graph,G. In order to do so, we study the probability that a random walk on a random graph returns to its originating vertex at thek-th step, for various values ofk. Our main theorem about eigenvalues is that $$E|\lambda _2 (G)|^m \leqslant \left( {2\sqrt {2d - 1} \left( {1 + \frac{{\log d}}{{\sqrt {2d} }} + 0\left( {\frac{1}{{\sqrt d }}} \right)} \right) + 0\left( {\frac{{d^{3/2} \log \log n}}{{\log n}}} \right)} \right)^m $$ for any \(m \leqslant 2\left\lfloor {log n\left\lfloor {\sqrt {2d - } 1/2} \right\rfloor /\log d} \right\rfloor \) , where E denotes the expected value over a certain probability space of 2d-regular graphs. It follows, for example, that for fixedd the second eigenvalue's magnitude is no more than \(2\sqrt {2d - 1} + 2\log d + C'\) with probability 1?n ^?C for constantsC andC′ for sufficiently largen.