On the girth of extremal graphs without shortest cycles

Let EX(ν;{C₃,…,C_n}) denote the set of graphs G of order ν that contain no cycles of length less than or equal to n which have maximum number of edges. In this paper we consider a problem posed by several authors: does G contain an n+1 cycle? We prove that the diameter of G is at most n−1, and present several results concerning the above question: the girth of G is g=n+1 if (i) ν≥n+5, diameter equal to n−1 and minimum degree at least 3; (ii) ν≥12, ν∉{15,80,170} and n=6. Moreover, if ν=15 we find an extremal graph of girth 8 obtained from a 3-regular complete bipartite graph subdividing its edges. (iii) We prove that if ν≥2n−3 and n≥7 the girth is at most 2n−5. We also show that the answer to the question is negative for ν≤n+1+⌊(n−2)/2⌋.     

New families of graphs without short cycles and large size

We denote by ex(n;{C₃,C₄,…,C_s}) or f_s(n) the maximum number of edges in a graph of order n and girth at least s+1. First we give a method to transform an n-vertex graph of girth g into a graph of girth at least g−1 on fewer vertices. For an infinite sequence of values of n and s∈{4,6,10} the obtained graphs are denser than the known constructions of graphs of the same girth s+1. We also give another different construction of dense graphs for an infinite sequence of values of n and s∈{7,11}. These two methods improve the known lower bounds on f_s(n) for s∈{4,6,7,10,11} which were obtained using different algorithms. Finally, to know how good are our results, we have proved that for s∈{5,7,11}, and for s∈{6,10}.     

On 2-factors with cycles containing specified edges in a bipartite graph

Let k≥1 be an integer and G=(V₁,V₂;E) a bipartite graph with |V₁|=|V₂|=n such that n≥2k+2. In this paper it has been proved that if for each pair of nonadjacent vertices x∈V₁ and y∈V₂, , then for any k independent edges e₁,…,e_k of G, G has a 2-factor with k+1 cycles C₁,…,C_k+1 such that e_i∈E(C_i) and |V(C_i)|=4 for each i∈{1,…,k}. We shall also show that the conditions in this paper are sharp.     

A generalization of Fan’s results: Distribution of cycle lengths in graphs

Fan [G. Fan, Distribution of cycle lengths in graphs, J. Combin. Theory Ser. B 84 (2002) 187-202] proved that if G is a graph with minimum degree δ(G)≥3k for any positive integer k, then G contains k+1 cycles C₀,C₁,…,C_k such that k+1<|E(C₀)|<|E(C₁)|<?<|E(C_k)|, |E(C_i)−E(C_i−1)|=2, 1≤i≤k−1, and 1≤|E(C_k)|−|E(C_k−1)|≤2, and furthermore, if δ(G)≥3k+1, then |E(C_k)|−|E(C_k−1)|=2. In this paper, we generalize Fan’s result, and show that if we let G be a graph with minimum degree δ(G)≥3, for any positive integer k (if k≥2, then δ(G)≥4), if d_G(u)+d_G(v)≥6k−1 for every pair of adjacent vertices u,v∈V(G), then G contains k+1 cycles C₀,C₁,…,C_k such that k+1<|E(C₀)|<|E(C₁)|<?<|E(C_k)|, |E(C_i)−E(C_i−1)|=2, 1≤i≤k−1, and 1≤|E(C_k)|−|E(C_k−1)|≤2, and furthermore, if d_G(u)+d_G(v)≥6k+1, then |E(C_k)|−|E(C_k−1)|=2.     

Total edge irregularity strength of complete graphs and complete bipartite graphs

A total edge irregular k-labelling ν of a graph G is a labelling of the vertices and edges of G with labels from the set {1,…,k} in such a way that for any two different edges e and f their weights φ(f) and φ(e) are distinct. Here, the weight of an edge g=uv is φ(g)=ν(g)+ν(u)+ν(v), i. e. the sum of the label of g and the labels of vertices u and v. The minimum k for which the graph G has an edge irregular total k-labelling is called the total edge irregularity strength of G.We have determined the exact value of the total edge irregularity strength of complete graphs and complete bipartite graphs.     

On a conjecture of Erdős and Simonovits: Even cycles

Let F be a family of graphs. A graph is F-free if it contains no copy of a graph in F as a subgraph. A cornerstone of extremal graph theory is the study of the Turán number ex(n,F), the maximum number of edges in an F-free graph on n vertices. Define the Zarankiewicz number z(n,F) to be the maximum number of edges in an F-free bipartite graph on n vertices. Let C _k denote a cycle of length k, and let C _k denote the set of cycles C _?, where 3≤?≤k and ? and k have the same parity. Erd?s and Simonovits conjectured that for any family F consisting of bipartite graphs there exists an odd integer k such that ex(n,F ∪ C _k ) ～ z(n,F) — here we write f(n) ～ g(n) for functions f,g: ? → ? if lim _n→∞ f(n)/g(n)=1. They proved this when F ={C ₄} by showing that ex(n,{C ₄;C ₅})～z(n,C ₄). In this paper, we extend this result by showing that if ?∈{2,3,5} and k>2? is odd, then ex(n,C _2? ∪{C _k }) ～ z(n,C _2? ). Furthermore, if k>2?+2 is odd, then for infinitely many n we show that the extremal C _2? ∪{C _k }-free graphs are bipartite incidence graphs of generalized polygons. We observe that this exact result does not hold for any odd k<2?, and furthermore the asymptotic result does not hold when (?,k) is (3, 3), (5, 3) or (5, 5). Our proofs make use of pseudorandomness properties of nearly extremal graphs that are of independent interest.     

On extremal k-outconnected graphs

Let G be a minimally k-connected graph with n nodes and m edges. Mader proved that if n?3k-2 then m?k(n-k), and for n?3k-1 an equality is possible if, and only if, G is the complete bipartite graph K_k,n-k. Cai proved that if n?3k-2 then m?⌊(n+k)²/8⌋, and listed the cases when this bound is tight.In this paper we prove a more general theorem, which implies similar results for minimally k-outconnected graphs; a graph is called k-outconnected from r if it contains k internally disjoint paths from r to every other node.     

Properties of connected graphs having minimum degree distance

The degree distance of a connected graph, introduced by Dobrynin, Kochetova and Gutman, has been studied in mathematical chemistry. In this paper some properties of graphs having minimum degree distance in the class of connected graphs of order n and size m≥n−1 are deduced. It is shown that any such graph G has no induced subgraph isomorphic to P₄, contains a vertex z of degree n−1 such that G−z has at most one connected component C such that |C|≥2 and C has properties similar to those of G.For any fixed k such that k=0,1 or k≥3, if m=n+k and n≥k+3 then the extremal graph is unique and it is isomorphic to K₁+(K_1,k+1∪(n−k−3)K₁).     

Vertex pancyclicity in quasi claw-free graphs

This paper generalizes the concept of locally connected graphs. A graph G is triangularly connected if for every pair of edges e₁,e₂∈E(G), G has a sequence of 3-cycles C₁,C₂,…,C_l such that e₁∈C₁,e₂∈C_l and E(C_i)∩E(C_i+1)≠∅ for 1?i?l-1. In this paper, we show that every triangularly connected quasi claw-free graph on at least three vertices is vertex pancyclic. Therefore, the conjecture proposed by Ainouche is solved.     

A quadratic programming approach to the Randić index

Let G(k, n) be the set of connected graphs without multiple edges or loops which have n vertices and the minimum degree of vertices is k. The Randi? index χ = χ(G) of a graph G   is defined by χ(G)=_∑(uv)(_δuδv)^-1/2$\chi (G)={\sum }_{(\mathit{uv})}({\delta }_u{\delta }_v{)}^{-1/2}$, where δ_u is the degree of vertex u and the summation extends over all edges (uv) of G. Caporossi et al. [G. Caporossi, I. Gutman, P. Hansen, Variable neighborhood search for extremal graphs IV: Chemical trees with extremal connectivity index, Computers and Chemistry 23 (1999) 469–477] proposed the use of linear programming as one of the tools for finding the extremal graphs. In this paper we introduce a new approach based on quadratic programming for finding the extremal graphs in G(k, n) for this index. We found the extremal graphs or gave good bounds for this index when the number n_k of vertices of degree k is between n − k and n. We also tried to find the graphs for which the Randi? index attained its minimum value with given k (k ? n/2) and n. We have solved this problem partially, that is, we have showed that the extremal graphs must have the number n_k of vertices of degree k less or equal n − k and the number of vertices of degree n − 1 less or equal k.     

Two new methods to obtain super vertex-magic total labelings of graphs

Let G=(V,E) be a finite non-empty graph, where V and E are the sets of vertices and edges of G, respectively, and |V|=n and |E|=e. A vertex-magic total labeling (VMTL) is a bijection λ from V∪E to the consecutive integers 1,2,…,n+e with the property that for every v∈V, , for some constant h. Such a labeling is super if λ(V)={1,2,…,n}. In this paper, two new methods to obtain super VMTLs of graphs are put forward. The first, from a graph G with some characteristics, provides a super VMTL to the graph kG graph composed by the disjoint unions of k copies of G, for a large number of values of k. The second, from a graph G₀ which admits a super VMTL; for instance, the graph kG, provides many super VMTLs for the graphs obtained from G₀ by means of the addition to it of various sets of edges.     

Two equivalent measures on weighted hypergraphs

Let H=(N,E,w) be a hypergraph with a node set N={0,1,…,n-1}, a hyperedge set E⊆2^N, and real edge-weights w(e) for e∈E. Given a convex n-gon P in the plane with vertices x₀,x₁,…,x_n-1 which are arranged in this order clockwisely, let each node i∈N correspond to the vertex x_i and define the area A_P(H) of H on P by the sum of the weighted areas of convex hulls for all hyperedges in H. For 0?i<j<k?n-1, a convex three-cut C(i,j,k) of N is {{i,…,j-1}, {j,…,k-1}, {k,…,n-1,0,…,i-1}} and its size c_H(i,j,k) in H is defined as the sum of weights of edges e∈E such that e contains at least one node from each of {i,…,j-1}, {j,…,k-1} and {k,…,n-1,0,…,i-1}. We show that the following two conditions are equivalent:

•

A_P(H)?A_P(H^′) for all convex n-gons P.

•

c_H(i,j,k)?c_H^′(i,j,k) for all convex three-cuts C(i,j,k).

From this property, a polynomial time algorithm for determining whether or not given weighted hypergraphs H and H^′ satisfy “A_P(H)?A_P(H^′) for all convex n-gons P” is immediately obtained.     

A note on traversing specified vertices in graphs embedded with large representativity

A graph G is said to have property P(2,k) if given any k+2 distinct vertices a,b,v₁,…,v_k, there is a path P in G joining a and b and passing through all of v₁,…,v_k. A graph G is said to have property C(k) if given any k distinct vertices v₁,…,v_k, there is a cycle C in G containing all of v₁,…,v_k. It is shown that if a 4-connected graph G is embedded in an orientable surface Σ (other than the sphere) of Euler genus eg(G,Σ), with sufficiently large representativity (as a function of both eg(G,Σ) and k), then G possesses both properties P(2,k) and C(k).     

Uniformly optimal graphs in some classes of graphs with node failures

The uniformly optimal graph problem with node failures consists of finding the most reliable graph in the class Ω(n,m) of all graphs with n nodes and m edges in which nodes fail independently and edges never fail. The graph G is called uniformly optimal in Ω(n,m) if, for all node-failure probabilities q∈(0,1), the graph G is the most reliable graph in the class of graphs Ω(n,m). This paper proves that the multipartite graphs K(b,b+1,…,b+1,b+2) are uniformly optimal in their classes Ω((k+2)(b+1),(k²+3k+2)(b+1)²/2−1), where k is the number of partite sets of size (b+1), while for i>2, the multipartite graphs K(b,b+1,…,b+1,b+i) are not uniformly optimal in their classes Ω((k+2)b+k+i,(k+2)(k+1)b²/2+(k+1)(k+i)b+k(k+2i−1)/2).     

Bipartite rainbow numbers of matchings

Given two graphs G and H, let f(G,H) denote the maximum number c for which there is a way to color the edges of G with c colors such that every subgraph H of G has at least two edges of the same color. Equivalently, any edge-coloring of G with at least rb(G,H)=f(G,H)+1 colors contains a rainbow copy of H, where a rainbow subgraph of an edge-colored graph is such that no two edges of it have the same color. The number rb(G,H) is called the rainbow number ofHwith respect toG, and simply called the bipartite rainbow number ofH if G is the complete bipartite graph K_m,n. Erd?s, Simonovits and Sós showed that rb(K_n,K₃)=n. In 2004, Schiermeyer determined the rainbow numbers rb(K_n,K_k) for all n≥k≥4, and the rainbow numbers rb(K_n,kK₂) for all k≥2 and n≥3k+3. In this paper we will determine the rainbow numbers rb(K_m,n,kK₂) for all k≥1.     

Vertex-disjoint quadrilaterals containing specified edges in a bipartite graph

The theory of vertex-disjoint cycles and 2-factors of graphs is the extension and generation of the well-known Hamiltonian cycles theory and it has important applications in network communication. In this paper we first prove the following result. Let G=(V ₁,V ₂;E) be a bipartite graph with |V ₁|=|V ₂|=n such that n≥2k+1, where k≥1 is an integer. If d(x)+d(y)≥?(4n+2k?1)/3? for each pair of nonadjacent vertices x and y of G with x∈V ₁ and y∈V ₂, then, for any k independent edges e ₁,…,e _k of G, G contains k vertex-disjoint quadrilaterals C ₁,…,C _k such that e _i ∈E(C _i ) for each i∈{1,…,k}. We further show that the degree condition above is sharp. If |V ₁|=|V ₂|=2k, we give degree conditions that G has a 2-factor with k vertex-disjoint quadrilaterals C ₁,…,C _k containing specified edges of G.     

Critically indecomposable graphs

An undirected graph G=(V,E) with a specific subset X⊂V is called X-critical if G and G(X), induced subgraph on X, are indecomposable but G(V−{w}) is decomposable for every w∈V−X. This is a generalization of critically indecomposable graphs studied by Schmerl and Trotter [J.H. Schmerl, W.T. Trotter, Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures, Discrete Mathematics 113 (1993) 191-205] and Bonizzoni [P. Bonizzoni, Primitive 2-structures with the (n−2)-property, Theoretical Computer Science 132 (1994) 151-178], who deal with the case where X is empty.We present several structural results for this class of graphs and show that in every X-critical graph the vertices of V−X can be partitioned into pairs (a₁,b₁),(a₂,b₂),…,(a_m,b_m) such that G(V−{a_j1,b_j1,…,a_jk,b_jk}) is also an X-critical graph for arbitrary set of indices {j₁,…,j_k}. These vertex pairs are called commutative elimination sequence. If G is an arbitrary indecomposable graph with an indecomposable induced subgraph G(X), then the above result establishes the existence of an indecomposability preserving sequence of vertex pairs (x₁,y₁),…,(x_t,y_t) such that x_i,y_i∈V−X. As an application of the commutative elimination sequence of an X-critical graph we present algorithms to extend a 3-coloring (similarly, 1-factor) of G(X) to entire G.     

The Crossing Number of C(mk;{1, k})

Calculating the crossing number of a given graph is, in general, an elusive problem. Garey and Johnson have proved that the problem of determining the crossing number of an arbitrary graph is NP-complete. The crossing number of a network(graph) is closely related to the minimum layout area required for the implementation of a VLSI circuit for that network. With this important application in mind, it makes most sense to analyze the the crossing number of graphs with good interconnection properties, such as the circulant graphs. In this paper we study the crossing number of the circulant graph C(mk;{1,k}) for m3, k3, give an upper bound of cr(C(mk;{1,k})), and prove that cr(C(3k;{1,k}))=k.Research supported by Chinese Natural Science Foundation     

Edge-deletable IM-extendable graphs with minimum number of edges

A graph G is induced matching extendable, shortly IM-extendable, if every induced matching of G is included in a perfect matching of G. For a nonnegative integer k, a graph G is called a k-edge-deletable IM-extendable graph, if, for every F⊆E(G) with |F|=k, G−F is IM-extendable. In this paper, we characterize the k-edge-deletable IM-extendable graphs with minimum number of edges. We show that, for a positive integer k, if G is ak-edge-deletable IM-extendable graph on 2n vertices, then |E(G)|≥(k+2)n; furthermore, the equality holds if and only if either G≅K_k+2,k+2, or k=4r−2 for some integer r≥3 and G≅C₅[N_2r], where N_2r is the empty graph on 2r vertices and C₅[N_2r] is the graph obtained from C₅ by replacing each vertex with a graph isomorphic to N_2r.