Some relations between rank of a graph and its complement

Let G be a graph of order n and rank(G) denotes the rank of its adjacency matrix. Clearly, . In this paper we characterize all graphs G such that or n + 2. Also for every integer n ? 5 and any k, 0 ? k ? n, we construct a graph G of order n, such that .     

Colorings at minimum cost

We define by min_c∑_{u,v}∈E(G)|c(u)−c(v)| the min-costMC(G) of a graph G, where the minimum is taken over all proper colorings c. The min-cost-chromatic numberχ_M(G) is then defined to be the (smallest) number of colors k for which there exists a proper k-coloring c attaining MC(G). We give constructions of graphs G where χ(G) is arbitrarily smaller than χ_M(G). On the other hand, we prove that for every 3-regular graph G^′, χ_M(G^′)≤4 and for every 4-regular line graph G^″, χ_M(G^″)≤5. Moreover, we show that the decision problem whether χ_M(G)=k is -hard for k≥3.     

Distributing vertices along a Hamiltonian cycle in Dirac graphs

A graph G on n vertices is called a Dirac graph if it has a minimum degree of at least n/2. The distance is defined as the number of edges in a shortest path of G joining u and v. In this paper we show that in a Dirac graph G, for every small enough subset S of the vertices, we can distribute the vertices of S along a Hamiltonian cycle C of G in such a way that all but two pairs of subsequent vertices of S have prescribed distances (apart from a difference of at most 1) along C. More precisely we show the following. There are ω,n₀>0 such that if G is a Dirac graph on n≥n₀ vertices, d is an arbitrary integer with 3≤d≤ωn/2 and S is an arbitrary subset of the vertices of G with 2≤|S|=k≤ωn/d, then for every sequence d_i of integers with 3≤d_i≤d,1≤i≤k−1, there is a Hamiltonian cycle C of G and an ordering of the vertices of S, a₁,a₂,…,a_k, such that the vertices of S are visited in this order on C and we have

     

Note on the energy of regular graphs

For a simple graph G, the energy E(G) is defined as the sum of the absolute values of all the eigenvalues of its adjacency matrix A(G). Let n,m, respectively, be the number of vertices and edges of G. One well-known inequality is that , where λ₁ is the spectral radius. If G is k-regular, we have . Denote . Balakrishnan [R. Balakrishnan, The energy of a graph, Linear Algebra Appl. 387 (2004) 287-295] proved that for each ?>0, there exist infinitely many n for each of which there exists a k-regular graph G of order n with k<n-1 and , and proposed an open problem that, given a positive integer n?3, and ?>0, does there exist a k-regular graph G of order n such that . In this paper, we show that for each ?>0, there exist infinitely many such n that . Moreover, we construct another class of simpler graphs which also supports the first assertion that .     

Laplacian energy of a graph

Let G be a graph with n vertices and m edges. Let λ₁, λ₂, … , λ_n be the eigenvalues of the adjacency matrix of G, and let μ₁, μ₂, … , μ_n be the eigenvalues of the Laplacian matrix of G. An earlier much studied quantity is the energy of the graph G. We now define and investigate the Laplacian energy as . There is a great deal of analogy between the properties of E(G) and LE(G), but also some significant differences.     

Complexity results in graph reconstruction

We investigate the relative complexity of the graph isomorphism problem (GI) and problems related to the reconstruction of a graph from its vertex-deleted or edge-deleted subgraphs (in particular, deck checking (DC) and legitimate deck (LD) problems). We show that these problems are closely related for all amounts c?1 of deletion:

(1)

, , , and .

(2)

For all k?2, and .

(3)

For all k?2, .

(4)

.

(5)

For all k?2, .

For many of these results, even the c=1 case was not previously known.Similar to the definition of reconstruction numbers vrn_∃(G) [F. Harary, M. Plantholt, The graph reconstruction number, J. Graph Theory 9 (1985) 451-454] and ern_∃(G) (see [J. Lauri, R. Scapellato Topics in Graph Automorphism and Reconstruction, London Mathematical Society, Cambridge University Press, Cambridge, 2003, p. 120]), we introduce two new graph parameters, vrn_∀(G) and ern_∀(G), and give an example of a family {G_n}_n?4 of graphs on n vertices for which vrn_∃(G_n)<vrn_∀(G_n). For every k?2 and n?1, we show that there exists a collection of k graphs on (2^k-1+1)n+k vertices with 2ⁿ 1-vertex-preimages, i.e., one has families of graph collections whose number of 1-vertex-preimages is huge relative to the size of the graphs involved.     

Extra edge connectivity and isoperimetric edge connectivity

An edge set S of a connected graph G is a k-extra edge cut, if G-S is no longer connected, and each component of G-S has at least k vertices. The cardinality of a minimum k-extra edge cut, denoted by λ_k(G), is the k-extra edge connectivity of G. The kth isoperimetric edge connectivity γ_k(G) is defined as , where ω(U) is the number of edges with one end in U and the other end in . Write β_k(G)=min{ω(U):U⊂V(G),|U|=k}. A graph G with is said to be γ_k-optimal.In this paper, we first prove that λ_k(G)=γ_k(G) if G is a regular graph with girth g?k/2. Then, we show that except for K_3,3 and K₄, a 3-regular vertex/edge transitive graph is γ_k-optimal if and only if its girth is at least k+2. Finally, we prove that a connected d-regular edge-transitive graph with d?6e_k(G)/k is γ_k-optimal, where e_k(G) is the maximum number of edges in a subgraph of G with order k.     

On the spanning fan-connectivity of graphs

Let G be a graph. The connectivity of G, κ(G), is the maximum integer k such that there exists a k-container between any two different vertices. A k-container of G between u and v, C_k(u,v), is a set of k-internally-disjoint paths between u and v. A spanning container is a container that spans V(G). A graph G is k^∗-connected if there exists a spanning k-container between any two different vertices. The spanning connectivity of G, κ^∗(G), is the maximum integer k such that G is w^∗-connected for 1≤w≤k if G is 1^∗-connected.Let x be a vertex in G and let U={y₁,y₂,…,y_k} be a subset of V(G) where x is not in U. A spanningk−(x,U)-fan, F_k(x,U), is a set of internally-disjoint paths {P₁,P₂,…,P_k} such that P_i is a path connecting x to y_i for 1≤i≤k and . A graph G is k^∗-fan-connected (or -connected) if there exists a spanning F_k(x,U)-fan for every choice of x and U with |U|=k and x∉U. The spanning fan-connectivity of a graph G, , is defined as the largest integer k such that G is -connected for 1≤w≤k if G is -connected.In this paper, some relationship between κ(G), κ^∗(G), and are discussed. Moreover, some sufficient conditions for a graph to be -connected are presented. Furthermore, we introduce the concept of a spanning pipeline-connectivity and discuss some sufficient conditions for a graph to be k^∗-pipeline-connected.     

On the Hadwiger's conjecture for graph products

The Hadwiger number η(G) of a graph G is the largest integer h such that the complete graph on h nodes K_h is a minor of G. Equivalently, η(G) is the largest integer such that any graph on at most η(G) nodes is a minor of G. The Hadwiger's conjecture states that for any graph G, η(G)?χ(G), where χ(G) is the chromatic number of G. It is well-known that for any connected undirected graph G, there exists a unique prime factorization with respect to Cartesian graph products. If the unique prime factorization of G is given as G₁□G₂□?□G_k, where each G_i is prime, then we say that the product dimension of G is k. Such a factorization can be computed efficiently.In this paper, we study the Hadwiger's conjecture for graphs in terms of their prime factorization. We show that the Hadwiger's conjecture is true for a graph G if the product dimension of G is at least . In fact, it is enough for G to have a connected graph M as a minor whose product dimension is at least , for G to satisfy the Hadwiger's conjecture. We show also that if a graph G is isomorphic to F^d for some F, then η(G)?χ(G)^{⌊(d-1)/2⌋}, and thus G satisfies the Hadwiger's conjecture when d?3. For sufficiently large d, our lower bound is exponentially higher than what is implied by the Hadwiger's conjecture.Our approach also yields (almost) sharp lower bounds for the Hadwiger number of well-known graph products like d-dimensional hypercubes, Hamming graphs and the d-dimensional grids. In particular, we show that for the d-dimensional hypercube H_d, . We also derive similar bounds for G^d for almost all G with n nodes and at least edges.     

4-regular claw-free IM-extendable graphs

A graph G is induced matching extendable (shortly, IM-extendable), if every induced matching of G is included in a perfect matching of G. A graph G is claw-free, if G does not contain any induced subgraph isomorphic to K_1,3. The kth power of a graph G, denoted by G^k, is the graph with vertex set V(G) in which two vertices are adjacent if and only if the distance between them in G is at most k. In this paper, the 4-regular claw-free IM-extendable graphs are characterized. It is shown that the only 4-regular claw-free connected IM-extendable graphs are , and T_r, r?2, where T_r is the graph with 4r vertices u_i,v_i,x_i,y_i, 1?i?r, such that for each i with 1?i?r, {u_i,v_i,x_i,y_i} is a clique of T_r and . We also show that a 4-regular strongly IM-extendable graph must be claw-free. As a consequence, the only 4-regular strongly IM-extendable graphs are K₄×K₂, and .     

Walks and the spectral radius of graphs

Given a graph G, write μ(G) for the largest eigenvalue of its adjacency matrix, ω(G) for its clique number, and w_k(G) for the number of its k-walks. We prove that the inequalities

     

The asymptotic number of spanning trees in circulant graphs

Let T(G) be the number of spanning trees in graph G. In this note, we explore the asymptotics of T(G) when G is a circulant graph with given jumps.The circulant graph is the 2k-regular graph with n vertices labeled 0,1,2,…,n−1, where node i has the 2k neighbors i±s₁,i±s₂,…,i±s_k where all the operations are . We give a closed formula for the asymptotic limit as a function of s₁,s₂,…,s_k. We then extend this by permitting some of the jumps to be linear functions of n, i.e., letting s_i, d_i and e_i be arbitrary integers, and examining

     

On the ratios between packing and domination parameters of a graph

The relationship ρ_L(G)≤ρ(G)≤γ(G) between the lower packing number ρ_L(G), the packing number ρ(G) and the domination number γ(G) of a graph G is well known. In this paper we establish best possible bounds on the ratios of the packing numbers of any (connected) graph to its six domination-related parameters (the lower and upper irredundance numbers ir and IR, the lower and upper independence numbers i and β, and the lower and upper domination numbers γ and Γ). In particular, best possible constants a_θ, b_θ, c_θ and d_θ are found for which the inequalities and hold for any connected graph G and all θ∈{ir,γ,i,β,Γ,IR}. From our work it follows, for example, that and for any connected graph G, and that these inequalities are best possible.     

Note on robust critical graphs with large odd girth

A graph G is (k+1)-critical if it is not k-colourable but G−e is k-colourable for any edge e∈E(G). In this paper we show that for any integers k≥3 and l≥5 there exists a constant c=c(k,l)>0, such that for all , there exists a (k+1)-critical graph G on n vertices with and odd girth at least ?, which can be made (k−1)-colourable only by the omission of at least cn² edges.     

Proof of conjecture involving the second largest signless Laplacian eigenvalue and the index of graphs

Let G = (V, E) be a simple graph. Denote by D(G) the diagonal matrix of its vertex degrees and by A(G) its adjacency matrix. Then the signless Laplacian matrix of G is Q(G) = D(G) + A(G). In [5], Cvetkovi? et al. have given the following conjecture involving the second largest signless Laplacian eigenvalue (q₂) and the index (λ₁) of graph G (see also Aouchiche and Hansen [1]):

     

Equitable colorings of Kronecker products of graphs

For a positive integer k, a graph G is equitably k-colorable if there is a mapping f:V(G)→{1,2,…,k} such that f(x)≠f(y) whenever xy∈E(G) and ||f⁻¹(i)|−|f⁻¹(j)||≤1 for 1≤i<j≤k. The equitable chromatic number of a graph G, denoted by χ₌(G), is the minimum k such that G is equitably k-colorable. The equitable chromatic threshold of a graph G, denoted by , is the minimum t such that G is equitably k-colorable for k≥t. The current paper studies equitable chromatic numbers of Kronecker products of graphs. In particular, we give exact values or upper bounds on χ₌(G×H) and when G and H are complete graphs, bipartite graphs, paths or cycles.     

Degree conditions for restricted-edge-connectivity and isoperimetric-edge-connectivity to be optimal

For a connected graph G=(V,E), an edge set S⊂E is a k-restricted-edge-cut, if G-S is disconnected and every component of G-S has at least k vertices. The k-restricted-edge-connectivity of G, denoted by λ_k(G), is defined as the cardinality of a minimum k-restricted-edge-cut. The k-isoperimetric-edge-connectivity is defined as , where is the set of edges with one end in U and the other end in . In this note, we give some degree conditions for a graph to have optimal λ_k and/or γ_k.     

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