More Like this

1. On the edit distance function of the random graph

   https://doi.org/10.1017/S0963548321000353  

   Martin, Ryan R.; Riasanovsky, Alex W. (March 2022, Combinatorics, Probability and Computing)

   Abstract Given a hereditary property of graphs $$\mathcal{H}$$ and a $$p\in [0,1]$$ , the edit distance function $$\textrm{ed}_{\mathcal{H}}(p)$$ is asymptotically the maximum proportion of edge additions plus edge deletions applied to a graph of edge density p sufficient to ensure that the resulting graph satisfies $$\mathcal{H}$$ . The edit distance function is directly related to other well-studied quantities such as the speed function for $$\mathcal{H}$$ and the $$\mathcal{H}$$ -chromatic number of a random graph. Let $$\mathcal{H}$$ be the property of forbidding an Erdős–Rényi random graph $$F\sim \mathbb{G}(n_0,p_0)$$ , and let $$\varphi$$ represent the golden ratio. In this paper, we show that if $$p_0\in [1-1/\varphi,1/\varphi]$$ , then a.a.s. as $$n_0\to\infty$$ , \begin{align*} {\textrm{ed}}_{\mathcal{H}}(p) = (1+o(1))\,\frac{2\log n_0}{n_0} \cdot\min\left\{ \frac{p}{-\log(1-p_0)}, \frac{1-p}{-\log p_0} \right\}. \end{align*} Moreover, this holds for $$p\in [1/3,2/3]$$ for any $$p_0\in (0,1)$$ . A primary tool in the proof is the categorization of p -core coloured regularity graphs in the range $$p\in[1-1/\varphi,1/\varphi]$$ . Such coloured regularity graphs must have the property that the non-grey edges form vertex-disjoint cliques. 

   more » « less
2. Edge Cover Through Edge Coloring

   https://doi.org/10.37236/13163  

   Chen, Guantao; Shan, Songling (April 2025, The Electronic Journal of Combinatorics)

   Let $$G$$ be a multigraph. A subset $$F$$ of $E(G)$ is an edge cover of $$G$$ if every vertex of $$G$$ is incident to an edge of $$F$$. The cover index, $$\xi(G)$$, is the largest number of edge covers into which the edges of $$G$$ can be partitioned. Clearly $$\xi(G) \le \delta(G)$$, the minimum degree of $$G$$. For $$U\subseteq V(G)$$, denote by $E^+(U)$ the set of edges incident to a vertex of $$U$$. When $|U|$ is odd, to cover all the vertices of $$U$$, any edge cover needs to contain at least $(|U|+1)/2$ edges from $E^+(U)$, indicating $$ \xi(G) \le |E^+(U)|/ ((|U|+1)/2)$$. Let $$\rho_c(G)$$, the co-density of $$G$$, be defined as the minimum of $|E^+(U)|/((|U|+1)/2)$ ranging over all $$U\subseteq V(G)$$, where $$|U| \ge 3$$ and $|U|$ is odd. Then $$\rho_c(G)$$ provides another upper bound on $$\xi(G)$$. Thus $$\xi(G) \le \min\{\delta(G), \lfloor \rho_c(G) \rfloor \}$$. For a lower bound on $$\xi(G)$$, in 1978, Gupta conjectured that $$\xi(G) \ge \min\{\delta(G)-1, \lfloor \rho_c(G) \rfloor \}$$. Gupta himself verified the conjecture for simple graphs, and Cao et al. recently verified this conjecture when $$\rho_c(G)$$ is not an integer. In this paper, we confirm the conjecture when the maximum multiplicity of $$G$$ is at most two or $$ \min\{\delta(G)-1, \lfloor \rho_c(G) \rfloor \} \le 6$$. The proof relies on a newly established result on edge colorings. The result holds independent interest and has the potential to significantly contribute towards resolving the conjecture entirely. 

   more » « less
3. Triangle-degrees in graphs and tetrahedron coverings in 3-graphs

   https://doi.org/10.1017/S0963548320000061  

   Falgas-Ravry, Victor; Markström, Klas; Zhao, Yi (March 2021, Combinatorics, Probability and Computing)

   null (Ed.)

   Abstract We investigate a covering problem in 3-uniform hypergraphs (3-graphs): Given a 3-graph F , what is c 1 ( n , F ), the least integer d such that if G is an n -vertex 3-graph with minimum vertex-degree $$\delta_1(G)>d$$ then every vertex of G is contained in a copy of F in G ? We asymptotically determine c 1 ( n , F ) when F is the generalized triangle $$K_4^{(3)-}$$ , and we give close to optimal bounds in the case where F is the tetrahedron $$K_4^{(3)}$$ (the complete 3-graph on 4 vertices). This latter problem turns out to be a special instance of the following problem for graphs: Given an n -vertex graph G with $m> n^2/4$ edges, what is the largest t such that some vertex in G must be contained in t triangles? We give upper bound constructions for this problem that we conjecture are asymptotically tight. We prove our conjecture for tripartite graphs, and use flag algebra computations to give some evidence of its truth in the general case. 

   more » « less
4. Constructing near spanning trees with few local inspections

   Levi, Reut; Moshkovitz, Guy; Ron, Dana; Rubinfeld, Ronitt; Shapira, Asaf (March 2017, Random structures & algorithms)

   Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. Motivated by several recent studies of local graph algorithms, we consider the following variant of this problem. Let G be a connected bounded-degree graph. Given an edge e in G we would like to decide whether e belongs to a connected subgraph math formula consisting of math formula edges (for a prespecified constant math formula), where the decision for different edges should be consistent with the same subgraph math formula. Can this task be performed by inspecting only a constant number of edges in G? Our main results are: We show that if every t-vertex subgraph of G has expansion math formula then one can (deterministically) construct a sparse spanning subgraph math formula of G using few inspections. To this end we analyze a “local” version of a famous minimum-weight spanning tree algorithm. We show that the above expansion requirement is sharp even when allowing randomization. To this end we construct a family of 3-regular graphs of high girth, in which every t-vertex subgraph has expansion math formula. We prove that for this family of graphs, any local algorithm for the sparse spanning graph problem requires inspecting a number of edges which is proportional to the girth. 

   more » « less
5. Removing Symmetry in Circulant Graphs and Point-Block Incidence Graphs

   https://doi.org/10.3390/math9020166  

   Brooks, Josephine; Carbonero, Alvaro; Vargas, Joseph; Florez, Rigoberto; Rooney, Brendan; Narayan, Darren A (January 2021, Mathematics)

   null (Ed.)

   An automorphism of a graph is a mapping of the vertices onto themselves such that connections between respective edges are preserved. A vertex v in a graph G is fixed if it is mapped to itself under every automorphism of G. The fixing number of a graph G is the minimum number of vertices, when fixed, fixes all of the vertices in G. The determination of fixing numbers is important as it can be useful in determining the group of automorphisms of a graph-a famous and difficult problem. Fixing numbers were introduced and initially studied by Gibbons and Laison, Erwin and Harary and Boutin. In this paper, we investigate fixing numbers for graphs with an underlying cyclic structure, which provides an inherent presence of symmetry. We first determine fixing numbers for circulant graphs, showing in many cases the fixing number is 2. However, we also show that circulant graphs with twins, which are pairs of vertices with the same neighbourhoods, have considerably higher fixing numbers. This is the first paper that investigates fixing numbers of point-block incidence graphs, which lie at the intersection of graph theory and combinatorial design theory. We also present a surprising result-identifying infinite families of graphs in which fixing any vertex fixes every vertex, thus removing all symmetries from the graph. 

   more » « less