Hyper- and reverse-Wiener indices of F-sums of graphs

The Wiener index W(G)=∑_{u,v}⊂V(G)d(u,v), the hyper-Wiener index and the reverse-Wiener index , where d(u,v) is the distance of two vertices u,v in G, d²(u,v)=d(u,v)², n=|V(G)| and D is the diameter of G. In [M. Eliasi, B. Taeri, Four new sums of graphs and their Wiener indices, Discrete Appl. Math. 157 (2009) 794-803], Eliasi and Taeri introduced the F-sums of two connected graphs. In this paper, we determine the hyper- and reverse-Wiener indices of the F-sum graphs and, subject to some condition, we present some exact expressions of the reverse-Wiener indices of the F-sum graphs.     

A proof of a conjecture on the Randić index of graphs with given girth

The Randić index R(G) of a graph G is defined by , where is the degree of a vertex u in G and the summation extends over all edges uv of G. Aouchiche, Hansen and Zheng proposed the following conjecture: For any connected graph on n≥3 vertices with Randić index R and girth g,

with equalities if and only if . This paper is devoted to giving a confirmative proof to this conjecture.     

On hamiltonian colorings for some graphs

For a connected graph G and any two vertices u and v in G, let D(u,v) denote the length of a longest u-v path in G. A hamiltonian coloring of a connected graph G of order n is an assignment c of colors (positive integers) to the vertices of G such that |c(u)−c(v)|+D(u,v)≥n−1 for every two distinct vertices u and v in G. The value of a hamiltonian coloring c is the maximum color assigned to a vertex of G. The hamiltonian chromatic number of G is taken over all hamiltonian colorings c of G. In this paper we discuss the hamiltonian chromatic number of graphs G with . As examples, we determine the hamiltonian chromatic number for a class of caterpillars, and double stars.     

Hall ratio of the Mycielski graphs

Let n(G) denote the number of vertices of a graph G and let α(G) be the independence number of G, the maximum number of pairwise nonadjacent vertices of G. The Hall ratio of a graph G is defined by

     

The exact domination number of the generalized Petersen graphs

Let G=(V,E) be a graph. A subset S⊆V is a dominating set of G, if every vertex u∈V−S is dominated by some vertex v∈S. The domination number, denoted by γ(G), is the minimum cardinality of a dominating set. For the generalized Petersen graph G(n), Behzad et al. [A. Behzad, M. Behzad, C.E. Praeger, On the domination number of the generalized Petersen graphs, Discrete Mathematics 308 (2008) 603-610] proved that and conjectured that the upper bound is the exact domination number. In this paper we prove this conjecture.     

Spectra of lifted Ramanujan graphs

A random n-lift of a base-graph G is its cover graph H on the vertices [n]×V(G), where for each edge uv in G there is an independent uniform bijection π, and H has all edges of the form (i,u),(π(i),v). A main motivation for studying lifts is understanding Ramanujan graphs, and namely whether typical covers of such a graph are also Ramanujan.Let G be a graph with largest eigenvalue λ₁ and let ρ be the spectral radius of its universal cover. Friedman (2003) [12] proved that every “new” eigenvalue of a random lift of G is with high probability, and conjectured a bound of ρ+o(1), which would be tight by results of Lubotzky and Greenberg (1995) [15]. Linial and Puder (2010) [17] improved Friedman?s bound to . For d-regular graphs, where λ₁=d and , this translates to a bound of O(d2/3), compared to the conjectured .Here we analyze the spectrum of a random n-lift of a d-regular graph whose nontrivial eigenvalues are all at most λ in absolute value. We show that with high probability the absolute value of every nontrivial eigenvalue of the lift is . This result is tight up to a logarithmic factor, and for λ?d2/3−ε it substantially improves the above upper bounds of Friedman and of Linial and Puder. In particular, it implies that a typical n-lift of a Ramanujan graph is nearly Ramanujan.     

The signed star domination numbers of the Cartesian product graphs

Let G be a graph with vertex set V(G) and edge set E(G). A function f:E(G)→{-1,1} is said to be a signed star dominating function of G if for every v∈V(G), where E_G(v)={uv∈E(G)|u∈V(G)}. The minimum of the values of , taken over all signed star dominating functions f on G, is called the signed star domination number of G and is denoted by γ_SS(G). In this paper, a sharp upper bound of γ_SS(G×H) is presented.     

Blow-up analysis for a system of heat equations with nonlinear flux which obey different laws

We consider a system of heat equations u_t=Δu and v_t=Δv in Ω×(0,T) completely coupled by nonlinear boundary conditions

We prove that the solutions always blow up in finite time for non-zero and non-negative initial values. Also, the blow-up only occurs on ∂Ω with

for p,q>0, 0≤α<1 and 0≤β<p.     

A new upper bound for the total vertex irregularity strength of graphs

We investigate the following modification of the well-known irregularity strength of graphs. Given a total weighting w of a graph G=(V,E) with elements of a set {1,2,…,s}, denote wt_G(v)=∑_evw(e)+w(v) for each vV. The smallest s for which exists such a weighting with wt_G(u)≠wt_G(v) whenever u and v are distinct vertices of G is called the total vertex irregularity strength of this graph, and is denoted by . We prove that for each graph of order n and with minimum degree δ>0.     

Multi solitary waves for nonlinear Schrödinger equations

We consider the nonlinear Schrödinger equation in for any d1, with a nonlinearity such that solitary waves exist and are stable. Let R_k(t,x) be K arbitrarily given solitary waves of the equation with different speeds v₁,v₂,…,v_K. In this paper, we prove that there exists a solution u(t) of the equation such that

     

Local-edge-connectivity in digraphs and oriented graphs

A digraph without any cycle of length two is called an oriented graph. The local-edge-connectivityλ(u,v) of two vertices u and v in a digraph or graph D is the maximum number of edge-disjoint u-v paths in D, and the edge-connectivity of D is defined as . Clearly, λ(u,v)?min{d⁺(u),d^-(v)} for all pairs u and v of vertices in D. Let δ(D) be the minimum degree of D. We call a graph or digraph D maximally edge-connected when λ(D)=δ(D) and maximally local-edge-connected when

λ(u,v)=min{d⁺(u),d^-(v)}     

Eigenvalues and degree deviation in graphs

Let G be a graph with n vertices and m edges and let μ(G) = μ₁(G) ? ? ? μ_n(G) be the eigenvalues of its adjacency matrix. Set s(G)=∑_u∈V(G)∣d(u)-2m/n∣. We prove that

     

The independence polynomial of rooted products of graphs

A stable (or independent) set in a graph is a set of pairwise nonadjacent vertices thereof. The stability numberα(G) is the maximum size of stable sets in a graph G. The independence polynomial of G is

     

A sufficient condition for pancyclability of graphs

Let G be a graph of order n and S be a vertex set of q vertices. We call G,S-pancyclable, if for every integer i with 3≤i≤q there exists a cycle C in G such that |V(C)∩S|=i. For any two nonadjacent vertices u,v of S, we say that u,v are of distance two in S, denoted by d_S(u,v)=2, if there is a path P in G connecting u and v such that |V(P)∩S|≤3. In this paper, we will prove that if G is 2-connected and for all pairs of vertices u,v of S with d_S(u,v)=2, , then there is a cycle in G containing all the vertices of S. Furthermore, if for all pairs of vertices u,v of S with d_S(u,v)=2, , then G is S-pancyclable unless the subgraph induced by S is in a class of special graphs. This generalizes a result of Fan [G. Fan, New sufficient conditions for cycles in graphs, J. Combin. Theory B 37 (1984) 221-227] for the case when S=V(G).