Graphs with maximum size and lower bounded girth

For integers n≥4 and ν≥n+1, let ex(ν;{C₃,…,C_n}) denote the maximum number of edges in a graph of order ν and girth at least n+1. The {C₃,…,C_n}-free graphs with order ν and size ex(ν;{C₃,…,C_n}) are called extremal graphs and denoted by EX(ν;{C₃,…,C_n}). We prove that given an integer k≥0, for each n≥2log₂(k+2) there exist extremal graphs with ν vertices, ν+k edges and minimum degree 1 or 2. Considering this idea we construct four infinite families of extremal graphs. We also see that minimal (r;g)-cages are the exclusive elements in EX(ν₀(r,g);{C₃,…,C_g−1}).     

On the structure of extremal graphs of high girth

Let n ≥ 3 be a positive integer, and let G be a simple graph of order v containing no cycles of length smaller than n + 1 and having the greatest possible number of edges (an extremal graph). Does G contain an n + 1-cycle? In this paper we establish some properties of extremal graphs and present several results where this question is answered affirmatively. For example, this is always the case for (i) v ≥ 8 and n = 5, or (ii) when v is large compared to n: v ≥ , where a = n - 3 - , n ≥ 12. On the other hand we prove that the answer to the question is negative for v = 2n + 2 ≥ 26. © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 147–153, 1997     

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 the girth and diameter of generalized Johnson graphs

Let $v>k>i$ be non-negative integers. The generalized Johnson graph, $J(v,k,i)$, is the graph whose vertices are the $k$-subsets of a $v$-set, where vertices $A$ and $B$ are adjacent whenever $|A\cap B|=i$. In this article, we derive general formulas for the girth and diameter of $J(v,k,i)$. Additionally, we provide a formula for the distance between any two vertices $A$ and $B$ in terms of the cardinality of their intersection.     

A family of regular graphs of girth 5

Murty [A generalization of the Hoffman-Singleton graph, Ars Combin. 7 (1979) 191-193.] constructed a family of (p^m+2)-regular graphs of girth five and order 2p^2m, where p?5 is a prime, which includes the Hoffman-Singleton graph [A.J. Hoffman, R.R. Singleton, On Moore graphs with diameters 2 and 3, IBM J. (1960) 497-504]. This construction gives an upper bound for the least number f(k) of vertices of a k-regular graph with girth 5. In this paper, we extend the Murty construction to k-regular graphs with girth 5, for each k. In particular, we obtain new upper bounds for f(k), k?16.     

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.     

Reconfiguration graphs of shortest paths

For a graph $G$ and$a,b\in V\left(G\right)$, the shortest path reconfiguration graph of $G$ with respect to $a$ and$b$ is denoted by $S(G,a,b)$. The vertex set of $S(G,a,b)$ is the set of all shortest paths between $a$ and$b$ in $G$. Two vertices in $V\left(S(G,a,b)\right)$ are adjacent, if their corresponding paths in $G$ differ by exactly one vertex. This paper examines the properties of shortest path graphs. Results include establishing classes of graphs that appear as shortest path graphs, decompositions and sums involving shortest path graphs, and the complete classification of shortest path graphs with girth 5 or greater. We include an infinite family of well structured examples, showing that the shortest path graph of a grid graph is an induced subgraph of a lattice.     

Properly colored hamilton cycles in edge-colored complete graphs

It is shown that, for ϵ>0 and n>n₀(ϵ), any complete graph K on n vertices whose edges are colored so that no vertex is incident with more than (1-1/\sqrt2-\epsilon)n edges of the same color contains a Hamilton cycle in which adjacent edges have distinct colors. Moreover, for every k between 3 and n any such K contains a cycle of length k in which adjacent edges have distinct colors. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11 , 179–186 (1997)     

On the girth of random Cayley graphs

We prove that random d‐regular Cayley graphs of the symmetric group asymptotically almost surely have girth at least (log_d‐1|G|)^1/2/2 and that random d‐regular Cayley graphs of simple algebraic groups over ??_q asymptotically almost surely have girth at least log _d‐1|G|/dim(G). For the symmetric p‐groups the girth is between loglog |G| and (log |G|)^α with α < 1. Several conjectures and open questions are presented. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Compatible Hamilton cycles in random graphs

A graph is Hamiltonian if it contains a cycle passing through every vertex. One of the cornerstone results in the theory of random graphs asserts that for edge probability , the random graph G(n, p) is asymptotically almost surely Hamiltonian. We obtain the following strengthening of this result. Given a graph , an incompatibility system over G is a family where for every , the set F_v is a set of unordered pairs . An incompatibility system is Δ‐bounded if for every vertex v and an edge e incident to v, there are at most Δ pairs in F_v containing e. We say that a cycle C in G is compatible with if every pair of incident edges of C satisfies . This notion is partly motivated by a concept of transition systems defined by Kotzig in 1968, and can be used as a quantitative measure of robustness of graph properties. We prove that there is a constant such that the random graph with is asymptotically almost surely such that for any μnp‐bounded incompatibility system over G, there is a Hamilton cycle in G compatible with . We also prove that for larger edge probabilities , the parameter μ can be taken to be any constant smaller than . These results imply in particular that typically in G(n, p) for , for any edge‐coloring in which each color appears at most μnp times at each vertex, there exists a properly colored Hamilton cycle. Furthermore, our proof can be easily modified to show that for any edge‐coloring of such a random graph in which each color appears on at most μnp edges, there exists a Hamilton cycle in which all edges have distinct colors (i.e., a rainbow Hamilton cycle). © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 49, 533–557, 2016     

Group edge choosability of planar graphs without adjacent short cycles

In this paper,we prove that 2-degenerate graphs and some planar graphs without adjacent short cycles are group(Δ(G)+1)-edge-choosable,and some planar graphs with large girth and maximum degree are groupΔ(G)-edge-choosable.     

Heavy cycles in 2-connected triangle-free weighted graphs

A weighted graph is one in which every edge e is assigned a nonnegative number, called the weight of e. The sum of the weights of the edges incident with a vertex v is called the weighted degree of v, denoted by dw(v). The weight of a cycle is defined as the sum of the weights of its edges. Fujisawa proved that if G is a 2-connected triangle-free weighted graph such that the minimum weighted degree of G is at least d, then G contains a cycle of weight at least 2d. In this paper, we proved that if G is a2-connected triangle-free weighted graph of even size such that dw(u) + dw(v) ≥ 2d holds for any pair of nonadjacent vertices u, v ∈ V(G), then G contains a cycle of weight at least 2d.     

Rainbow hamilton cycles in random graphs

One of the most famous results in the theory of random graphs establishes that the threshold for Hamiltonicity in the Erd?s‐Rényi random graph G_n,p is around . Much research has been done to extend this to increasingly challenging random structures. In particular, a recent result by Frieze determined the asymptotic threshold for a loose Hamilton cycle in the random 3‐uniform hypergraph by connecting 3‐uniform hypergraphs to edge‐colored graphs. In this work, we consider that setting of edge‐colored graphs, and prove a result which achieves the best possible first order constant. Specifically, when the edges of G_n,p are randomly colored from a set of (1 + o(1))n colors, with , we show that one can almost always find a Hamilton cycle which has the additional property that all edges are distinctly colored (rainbow).Copyright © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 44, 328‐354, 2014     

On the restricted connectivity and superconnectivity in graphs with given girth

The restricted connectivity κ^′(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 u has all its neighbors in X; the superconnectivity κ₁(G) is defined similarly, this time considering only vertices u in G-X, hence κ₁(G)?κ^′(G). The minimum edge-degree of G is ξ(G)=min{d(u)+d(v)-2:uv∈E(G)}, d(u) standing for the degree of a vertex u. In this paper, several sufficient conditions yielding κ₁(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 κ₁(G)=κ^′(G)=ξ(G) under some additional constraints.