Search

The xy-Menger number with respect to a given integer ℓ, for every two vertices x, y in a connected graph G, denoted by ζℓ(x, y), is the maximum number of internally disjoint xy-paths whose lengths are at most ℓ in G. The Menger number of G with respect to ℓ is defined as ζℓ(G) = min{ζℓ(x, y) : x, y ∈ V(G)}. In this paper we focus on the Menger number of the strong product G1 G2 of two connected graphs G1 and G2 with at least three vertices. We show that ζℓ(G1 G2) ≥ ζℓ(G1)ζℓ(G2) and furthermore, that ζℓ+2(G1 G2) ≥ ζℓ(G1)ζℓ(G2) + ζℓ(G1) + ζℓ(G2) if both G1 and G2 have girth at least 5. These bounds are best possible, and in particular, we prove that the last inequality is reached when G1 and G2 are maximally connected graphs. Ministerio de Educación y Ciencia MTM2011-28800-C02-02 Generalitat de Cataluña 1298 SGR2009

Let EX(@n;{C"3,...,C"n}) denote the set of graphs G of order @n 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>=n+5, diameter equal to n-1 and minimum degree at least 3; (ii) @n>=12, @n@?{15,80,170} and n=6. Moreover, if @n=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 @n>=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@?n+1+@?(n-2)/2@?.

By an ({r,m};g)-cage we mean a graph on a minimum number of vertices f({r,m};g) with degree set {r,m}, 2==8. Moreover, we obtain for any integer k>=2 that f({r,k(r-1)+1};6)=2k(r-1)^2+2r where r-1 a is prime power. This result supports the conjecture that f({r,m};6)=2(rm-m+1) for any r

A matched sum graph G of two graphs G"1 and G"2 of the same order is obtained from the union of G"1 and G"2 and from joining each vertex of G"1 with one vertex of G"2 according to one bijection f between the vertices in V(G"1) and V(G"2). When G"1=G"2=H then f is just a permutation of V(H) and the corresponding matched sum graph is a permutation graph H^f. In this paper, we derive lower bounds for the connectivity, edge-connectivity, and different conditional connectivities in matched sum graphs, and present sufficient conditions which guarantee maximum values for these conditional connectivities.

Let (X,Y) denote a bipartite graph with classes X and Y such that |X|=m and |Y|=n. A complete bipartite subgraph with s vertices in X and t vertices in Y is denoted by K(s,t). The Zarankiewicz problem consists in finding the maximum number of edges, denoted by z(m,n;s,t), of a bipartite graph (X,Y) with |X|=m and |Y|=n without a complete bipartite K(s,t) as a subgraph. First, we prove that z(m,n;s,t)=mn-(m+n-s-t+1) if max{m,n}⩽s+t-1. Then we characterize the family Z(m,n;s,t) of extremal graphs for the values of parameters described above. Finally, we study the s=t case. We give the exact value of z(m,n;t,t) if 2t⩽n⩽3t-1 and we characterize the extremal graphs if either n=2t or both 2t

Girth pairs were introduced by Harary and Kovács [Regular graphs with given girth pair, J. Graph Theory 7 (1983) 209–218]. The odd girth (even girth) of a graph is the length of a shortest odd (even) cycle. Let g denote the smaller of the odd and even girths, and let h denote the larger. Then (g,h) is called the girth pair of the graph. In this paper we prove that a graph with girth pair (g,h) such that g is odd and h⩾g+3 is even has high (vertex-)connectivity if its diameter is at most h-3. The edge version of all results is also studied.

A counterexample on a conjecture of Gyori related with C"2"l-free bipartite graphs is described.

The extremal number ex(n;TKp) denotes the maximum number of edges of a graph of order n containing no topological complete graph TKp as a subgraph. In this paper we give the exact value of the extremal number ex(n;TKp) for ⌈(7n+7)/12⌉⩽p

"Discrete Mathemetics Top Cited Article 2005-2010" The restricted connectivity κ′(G)κ′(G) of a connected graph G is defined as the minimum cardinality of a vertex-cut over all vertex-cuts X such that no vertex uu has all its neighbors in X; the superconnectivity κ1(G)κ1(G) is defined similarly, this time considering only vertices uu in G-XG-X, hence κ1(G)⩽κ′(G)κ1(G)⩽κ′(G). The minimum edge-degree of G is ξ(G)=min{d(u)+d(v)-2:uv∈E(G)}ξ(G)=min{d(u)+d(v)-2:uv∈E(G)}, d(u)d(u) standing for the degree of a vertex uu. In this paper, several sufficient conditions yielding κ1(G)⩾ξ(G)κ1(G)⩾ξ(G) are given, improving a previous related result by Fiol et al. [Short paths and connectivity in graphs and digraphs, Ars Combin. 29B (1990) 17–31] and guaranteeing κ1(G)=κ′(G)=ξ(G)κ1(G)=κ′(G)=ξ(G) under some additional constraints. Peer Reviewed Award-winning

For a connected graph G, the rth extraconnectivity @k"r(G) is defined as the minimum cardinality of a cutset X such that all remaining components after the deletion of the vertices of X have at least r+1 vertices. The standard connectivity and superconnectivity correspond to @k"0(G) and @k"1(G), respectively. The minimum r-tree degree of G, denoted by @x"r(G), is the minimum cardinality of N(T) taken over all trees [email protected]?G of order |V(T)|=r+1, N(T) being the set of vertices not in T that are neighbors of some vertex of T. When r=1, any such considered tree is just an edge of G. Then, @x"1(G) is equal to the so-called minimum edge-degree of G, defined as @x(G)=min{d(u)+d(v)-2:[email protected]?E(G)}, where d(u) stands for the degree of vertex u. A graph G is said to be optimally r-extraconnected, for short @k"r-optimal, if @k"r(G)>[email protected]"r(G). In this paper, we present some sufficient conditions that guarantee @k"r(G)>[email protected]"r(G) for r>=2. These results improve some previous related ones, and can be seen as a complement of some others which were obtained by the authors for r=1.

By an ({r,m};g)-cage we mean a graph on a minimum number of vertices f({r,m};g) with degree set {r,m}, 2⩽r

A counterexample on a conjecture of Györi related with C2l-free bipartite graphs is described.