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.     

On local connectivity of graphs with given clique number

For a vertex v of a graph G, we denote by d(v) the degree of v. The local connectivity κ(u, v) of two vertices u and v in a graph G is the maximum number of internally disjoint u –v paths in G, and the connectivity of G is defined as κ(G)=min{κ(u, v)|u, v∈V(G)}. Clearly, κ(u, v)?min{d(u), d(v)} for all pairs u and v of vertices in G. Let δ(G) be the minimum degree of G. We call a graph G maximally connected when κ(G)=δ(G) and maximally local connected when for all pairs u and v of distinct vertices in G. In 2006, Hellwig and Volkmann (J Graph Theory 52 (2006), 7–14) proved that a connected graph G with given clique number ω(G)?p of order n(G) is maximally connected when As an extension of this result, we will show in this work that these conditions even guarantee that G is maximally local connected. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 192–197, 2010     

Maximally edge-connected and vertex-connected graphs and digraphs: A survey

Let D be a graph or a digraph. If δ(D) is the minimum degree, λ(D) the edge-connectivity and κ(D) the vertex-connectivity, then κ(D)?λ(D)?δ(D) is a well-known basic relationship between these parameters. The graph or digraph D is called maximally edge-connected if λ(D)=δ(D) and maximally vertex-connected if κ(D)=δ(D). In this survey we mainly present sufficient conditions for graphs and digraphs to be maximally edge-connected as well as maximally vertex-connected. We also discuss the concept of conditional or restricted edge-connectivity and vertex-connectivity, respectively.     

Bandwidth of the strong product of two connected graphs

The bandwidth B(G) of a graph G is the minimum of the quantity max{|f(x)-f(y)|:xy∈E(G)} taken over all proper numberings f of G. The strong product of two graphs G and H, written as G(S_P)H, is the graph with vertex set V(G)×V(H) and with (u₁,v₁) adjacent to (u₂,v₂) if one of the following holds: (a) u₁ and v₁ are adjacent to u₂ and v₂ in G and H, respectively, (b) u₁ is adjacent to u₂ in G and v₁=v₂, or (c) u₁=u₂ and v₁ is adjacent to v₂ in H. In this paper, we investigate the bandwidth of the strong product of two connected graphs. Let G be a connected graph. We denote the diameter of G by D(G). Let d be a positive integer and let x,y be two vertices of G. Let denote the set of vertices v so that the distance between x and v in G is at most d. We define δ_d(G) as the minimum value of over all vertices x of G. Let denote the set of vertices z such that the distance between x and z in G is at most d-1 and z is adjacent to y. We denote the larger of and by . We define η(G)=1 if G is complete and η(G) as the minimum of over all pair of vertices x,y of G otherwise. Let G and H be two connected graphs. Among other results, we prove that if δ_D(H)(G)?B(G)D(H)+1 and B(H)=⌈(|V(H)|+η(H)-2)/D(H)⌉, then B(G(S_P)H)=B(G)|V(H)|+B(H). Moreover, we show that this result determines the bandwidth of the strong product of some classes of graphs. Furthermore, we study the bandwidth of the strong product of power of paths with complete bipartite graphs.     

Integers with dense divisors

Let 1=d₁(n)<d₂(n)<?<d_τ(n)=n be the sequence of all positive divisors of the integer n in increasing order. We say that the divisors of n are y-dense iff max_1?i<τ(n)d_i+1(n)/d_i(n)?y. Let D(x,y,z) be the number of positive integers not exceeding x whose divisors are y-dense and whose prime divisors are bigger than z, and let , and . We show that is equivalent, in a large region, to a function d(u,v) which satisfies a difference-differential equation. Using that equation we find that d(u,v)?(1−u/v)/(u+1) for v?3+ε. Finally, we show that d(u,v)=e^−γd(u)+O(1/v), where γ is Euler's constant and d(u)∼x⁻¹D(x,y,1), for fixed u. This leads to a new estimate for d(u).     

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

Hamilton cycles in digraphs of unitary matrices

A set S⊆V is called a q⁺-set (q^--set, respectively) if S has at least two vertices and, for every u∈S, there exists v∈S,v≠u such that N⁺(u)∩N⁺(v)≠∅ (N^-(u)∩N^-(v)≠∅, respectively). A digraph D is called s-quadrangular if, for every q⁺-set S, we have |∪{N⁺(u)∩N⁺(v):u≠v,u,v∈S}|?|S| and, for every q^--set S, we have |∪{N^-(u)∩N^-(v):u,v∈S)}?|S|. We conjecture that every strong s-quadrangular digraph has a Hamilton cycle and provide some support for this conjecture.     

Bounded-hops power assignment in ad hoc wireless networks

Motivated by topology control in ad hoc wireless networks, Power Assignment is a family of problems, each defined by a certain connectivity constraint (such as strong connectivity). The input consists of a directed complete weighted digraph G=(V,c) (that is, ). The power of a vertex u in a directed spanning subgraph H is given by , and corresponds to the energy consumption required for node u to transmit to all nodes v with uv∈E(H). The power of H is given by . Power Assignment seeks to minimize p(H) while H satisfies the given connectivity constraint.Min-Power Bounded-Hops Broadcast is a power assignment problem which has as additional input a positive integer d and a r∈V. The output H must be a r-rooted outgoing arborescence of depth at most d. We give an (O(logn),O(logn)) bicriteria approximation algorithm for Min-Power Bounded-Hops Broadcast: that is, our output has depth at most O(dlogn) and power at most O(logn) times the optimum solution.For the Euclidean case, when c(u,v)=c(v,u)=∥u,v∥^κ (here ∥u,v∥ is the Euclidean distance and κ is a constant between 2 and 5), the output of our algorithm can be modified to give a O((logn)^κ) approximation ratio. Previous results for Min-Power Bounded-Hops Broadcast are only exact algorithms based on dynamic programming for the case when the nodes lie on the line and c(u,v)=c(v,u)=∥u,v∥^κ.Our bicriteria results extend to Min-Power Bounded-Hops Strong Connectivity, where H must have a path of at most d edges in between any two nodes. Previous work for Min-Power Bounded-Hops Strong Connectivity consists only of constant or better approximation for special cases of the Euclidean case.     

Greedy F-colorings of graphs

Let G=(V,E) be a connected graph. For a symmetric, integer-valued function δ on V×V, where K is an integer constant, N₀ is the set of nonnegative integers, and Z is the set of integers, we define a C-mapping by F(u,v,m)=δ(u,v)+m−K. A coloring c of G is an F-coloring if F(u,v,|c(u)−c(v)|)?0 for every two distinct vertices u and v of G. The maximum color assigned by c to a vertex of G is the value of c, and the F-chromatic number F(G) is the minimum value among all F-colorings of G. For an ordering of the vertices of G, a greedy F-coloring c of s is defined by (1) c(v₁)=1 and (2) for each i with 1?i<n, c(v_i+1) is the smallest positive integer p such that F(v_j,v_i+1,|c(v_j)−p|)?0, for each j with 1?j?i. The greedy F-chromatic number gF(s) of s is the maximum color assigned by c to a vertex of G. The greedy F-chromatic number of G is gF(G)=min{gF(s)} over all orderings s of V. The Grundy F-chromatic number is GF(G)=max{gF(s)} over all orderings s of V. It is shown that gF(G)=F(G) for every graph G and every F-coloring defined on G. The parameters gF(G) and GF(G) are studied and compared for a special case of the C-mapping F on a connected graph G, where δ(u,v) is the distance between u and v and .     

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.     

The multiple originator broadcasting problem in graphs

Given a graph G and a vertex subset S of V(G), the broadcasting time with respect toS, denoted by b(G,S), is the minimum broadcasting time when using S as the broadcasting set. And the k-broadcasting number, denoted by b_k(G), is defined by b_k(G)=min{b(G,S)|S⊆V(G),|S|=k}.Given a graph G and two vertex subsets S, S^′ of V(G), define , d(S,S^′)=min{d(u,v)|u∈S, v∈S^′}, and for all v∈V(G). For all k, 1?k?|V(G)|, the k-radius of G, denoted by r_k(G), is defined as r_k(G)=min{d(G,S)|S⊆V(G), |S|=k}.In this paper, we study the relation between the k-radius and the k-broadcasting numbers of graphs. We also give the 2-radius and the 2-broadcasting numbers of the grid graphs, and the k-broadcasting numbers of the complete n-partite graphs and the hypercubes.     

Degree sum conditions for oriented forests in digraphs

Let F be an oriented forest with n vertices and m arcs and D be a digraph without loops and multiple arcs. In this note we prove that D contains a subdigraph isomorphic to F if D has at least n vertices and min{d⁺(u)+d⁺(v),d⁻(u)+d⁻(v),d⁺(u)+d⁻(v)}≥2m−1 for every pair of vertices u,v∈V(D) with uv∉A(D). This is a common generalization of two results of Babu and Diwan, one on the existence of forests in graphs under a degree sum condition and the other on the existence of oriented forests in digraphs under a minimum degree condition.     

An extremal problem on non-full colorable graphs

For a given graph G of order n, a k-L(2,1)-labelling is defined as a function f:V(G)→{0,1,2,…k} such that |f(u)-f(v)|?2 when d_G(u,v)=1 and |f(u)-f(v)|?1 when d_G(u,v)=2. The L(2,1)-labelling number of G, denoted by λ(G), is the smallest number k such that G has a k-L(2,1)-labelling. The hole index ρ(G) of G is the minimum number of integers not used in a λ(G)-L(2,1)-labelling of G. We say G is full-colorable if ρ(G)=0; otherwise, it will be called non-full colorable. In this paper, we consider the graphs with λ(G)=2m and ρ(G)=m, where m is a positive integer. Our main work generalized a result by Fishburn and Roberts [No-hole L(2,1)-colorings, Discrete Appl. Math. 130 (2003) 513-519].     

The partition of a strong tournament

A digraph T is strong if for every pair of vertices u and v there exists a directed path from u to v and a directed path from v to u. Denote the in-degree and out-degree of a vertex v of T by d^-(v) and d⁺(v), respectively. We define δ^-(T)=min_vV(T){d^-(v)} and δ⁺(T)=min_vV(T){d⁺(v)}. Let T₀ be a 7-tournament which contains no transitive 4-subtournament. In this paper, we obtain some conditions on a strong tournament which cannot be partitioned into two cycles. We show that a strong tournament T with n6 vertices such that TT₀ and max{δ⁺(T),δ^-(T)}3 can be partitioned into two cycles. Finally, we give a sufficient condition for a tournament to be partitioned into k cycles.     

A short proof of Fan's theorem

In this note, we give a new short proof of the following theorem: Let G be a 2-connected graph of order n. If for any two vertices u and v with d(u,v)=2,max{d(u),d(v)}?c/2, then the circumference of G is at least c, where 3?c?n and d(u,v) is the distance between u and v in G.     

Domination in a digraph and in its reverse

Let D be a digraph. By γ(D) we denote the domintaion number of D and by D⁻ we denote a digraph obtained by reversing all the arcs of D. In this paper we prove that for every δ≥3 and k≥1 there exists a simple strongly connected δ-regular digraph D_δ,k such that . Analogous theorem is obtained for total domination number provided that δ≥4.     

Hyperbolic conservation laws with nonlinear diffusion and nonlinear dispersion

We study scalar conservation laws with nonlinear diffusion and nonlinear dispersion terms (any ??1), the flux function f(u) being mth order growth at infinity. It is shown that if ε, δ=δ(ε) tend to 0, then the sequence {uε} of the smooth solutions converges to the unique entropy solution u∈L^∞(0,T_∗;Lq(R)) to the conservation law ut+fx(u)=0 in . The proof relies on the methods of compensated compactness, Young measures and entropy measure-valued solutions. Some new a priori estimates are carried out. In particular, our result includes the convergence result by Schonbek when b(λ)=λ, ?=1 and LeFloch and Natalini when ?=1.     

Eigenvalue distribution of second-order dynamic equations on time scales considered as fractals

Let T⊂[a,b] be a time scale with a,b∈T. In this paper we study the asymptotic distribution of eigenvalues of the following linear problem −uΔΔ=λuσ, with mixed boundary conditions αu(a)+βuΔ(a)=0=γu(ρ(b))+δuΔ(ρ(b)). It is known that there exists a sequence of simple eigenvalues k{λk}; we consider the spectral counting function , and we seek for its asymptotic expansion as a power of λ. Let d be the Minkowski (or box) dimension of T, which gives the order of growth of the number K(T,ε) of intervals of length ε needed to cover T, namely K(T,ε)≈εd. We prove an upper bound of N(λ) which involves the Minkowski dimension, N(λ,T)?Cλd/2, where C is a positive constant depending only on the Minkowski content of T (roughly speaking, its d-volume, although the Minkowski content is not a measure). We also consider certain limiting cases (d=0, infinite Minkowski content), and we show a family of self similar fractal sets where N(λ,T) admits two-side estimates.     

Co-degree density of hypergraphs

For an r-graph H, let C(H)=minSd(S), where the minimum is taken over all (r−1)-sets of vertices of H, and d(S) is the number of vertices v such that S∪{v} is an edge of H. Given a family F of r-graphs, the co-degree Turán number is the maximum of C(H) among all r-graphs H which contain no member of F as a subhypergraph. Define the co-degree density of a family F to be

     

On strong digraphs with a prescribed ultracenter

The (directed) distance from a vertex u to a vertex v in a strong digraph D is the length of a shortest u-v (directed) path in D. The eccentricity of a vertex v of D is the distance from v to a vertex furthest from v in D. The radius radD is the minimum eccentricity among the vertices of D and the diameter diamD is the maximum eccentricity. A central vertex is a vertex with eccentricity radD and the subdigraph induced by the central vertices is the center C(D). For a central vertex v in a strong digraph D with radD < diamD, the central distance c(v) of v is the greatest nonnegative integer n such that whenever d(v, x) n, then x is in C(D). The maximum central distance among the central vertices of D is the ultraradius uradD and the subdigraph induced by the central vertices with central distance uradD is the ultracenter UC(D). For a given digraph D, the problem of determining a strong digraph H with UC(H) = D and C(H) D is studied. This problem is also considered for digraphs that are asymmetric.