An official website of the United States government
Given a simple graph $$G$$, the irregularity strength of $$G$$, denoted $s(G)$, is the least positive integer $$k$$ such that there is a weight assignment on edges $$f: E(G) \to \{1,2,\dots, k\}$$ for which each vertex weight $$f^V(v):= \sum_{u: \{u,v\}\in E(G)} f(\{u,v\})$$ is unique amongst all $$v\in V(G)$$. In 1987, Faudree and Lehel conjectured that there is a constant $$c$$ such that $$s(G) \leq n/d + c$$ for all $$d$$-regular graphs $$G$$ on $$n$$ vertices with $d>1$, whereas it is trivial that $$s(G) \geq n/d$$. In this short note we prove that the Faudree-Lehel Conjecture holds when $$d \geq n^{0.8+\epsilon}$$ for any fixed $$\epsilon >0$$, with a small additive constant $c=28$ for $$n$$ large enough. Furthermore, we confirm the conjecture asymptotically by proving that for any fixed $$\beta\in(0,1/4)$$ there is a constant $$C$$ such that for all $$d$$-regular graphs $$G$$, $$s(G) \leq \frac{n}{d}(1+\frac{C}{d^{\beta}})+28$$, extending and improving a recent result of Przybyło that $$s(G) \leq \frac{n}{d}(1+ \frac{1}{\ln^{\epsilon/19}n})$$ whenever $$d\in [\ln^{1+\epsilon} n, n/\ln^{\epsilon}n]$$ and $$n$$ is large enough.
more »
« less
On 2-fold graceful graphs
A long-standing conjecture by Kotzig, Ringel, and Rosa states that every tree admits a graceful labeling. That is, for any tree $$T$$ with $$n$$~edges, it is conjectured that there exists a labeling $$f\colon V(T) \to \{0,1,\ldots,n\}$$ such that the set of induced edge labels $$\bigl\{ |f(u)-f(v)| : \{u,v\}\in E(T) \bigr\}$$ is exactly $$\{1,2,\ldots,n\}$$. We extend this concept to allow for multigraphs with edge multiplicity at most~$$2$$. A \emph{2-fold graceful labeling} of a graph (or multigraph) $$G$$ with $$n$$~edges is a one-to-one function $$f\colon V(G) \to \{0,1,\ldots,n\}$$ such that the multiset of induced edge labels is comprised of two copies of each element in $$\bigl\{ 1,2,\ldots, \lfloor n/2 \rfloor \bigr\}$$ and, if $$n$$ is odd, one copy of $$\bigl\{ \lceil n/2 \rceil \bigr\}$$. When $$n$$ is even, this concept is similar to that of 2-equitable labelings which were introduced by Bloom and have been studied for several classes of graphs. We show that caterpillars, cycles of length $$n \not\equiv 1 \pmod{4}$$, and complete bipartite graphs admit 2-fold graceful labelings. We also show that under certain conditions, the join of a tree and an empty graph (i.e., a graph with vertices but no edges) is $$2$$-fold graceful.
more »
« less
- Award ID(s):
- 1359300
- PAR ID:
- 10220717
- Date Published:
- Journal Name:
- Journal of Combinatorial Mathematics and Combinatorial Computing
- Volume:
- 114
- Page Range / eLocation ID:
- 77-98
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Generalized splines are an algebraic combinatorial framework that generalizes and unifies various established concepts across different fields, most notably the classical notion of splines and the topological notion of GKM theory. The former consists of piecewise polynomials on a combinatorial geometric object like a polytope, whose polynomial pieces agree to a specified degree of differentiability. The latter is a graph-theoretic construction of torus-equivariant cohomology that Shareshian and Wachs used to reformulate the well-known Stanley-Stembridge conjecture, a reformulation that was recently proven to hold by Brosnan and Chow and independently Guay-Paquet. This paper focuses on the theory of generalized splines. A generalized spline on a graph $$G$$ with each edge labeled by an ideal in a ring $$R$$ consists of a vertex-labeling by elements of $$R$$ so that the labels on adjacent vertices $u, v$ differ by an element of the ideal associated to the edge $uv$. We study the $$R$$-module of generalized splines and produce minimum generating sets for several families of graphs and edge-labelings: $1)$ for all graphs when the set of possible edge-labelings consists of at most two finitely-generated ideals, and $2)$ for cycles when the set of possible edge-labelings consists of principal ideals generated by elements of the form $(ax+by)^2$ in the polynomial ring $$\mathbb{C}[x,y]$$. We obtain the generators using a constructive algorithm that is suitable for computer implementation and give several applications, including contextualizing several results in the theory of classical (analytic) splines.more » « less
-
null (Ed.)Recently Cutler and Radcliffe proved that the graph on $$n$$ vertices with maximum degree at most $$r$$ having the most cliques is a disjoint union of $$\lfloor n/(r+1)\rfloor$$ cliques of size $r+1$ together with a clique on the remainder of the vertices. It is very natural also to consider this question when the limiting resource is edges rather than vertices. In this paper we prove that among graphs with $$m$$ edges and maximum degree at most $$r$$, the graph that has the most cliques of size at least two is the disjoint union of $$\bigl\lfloor m \bigm/\binom{r+1}{2} \bigr\rfloor$$ cliques of size $r+1$ together with the colex graph using the remainder of the edges.more » « less
-
Let $$N=\binom{n}{2}$$ and $$s\geq 2$$. Let $$e_{i,j},\,i=1,2,\ldots,N,\,j=1,2,\ldots,s$$ be $$s$$ independent permutations of the edges $$E(K_n)$$ of the complete graph $$K_n$$. A MultiTree is a set $$I\subseteq [N]$$ such that the edge sets $$E_{I,j}$$ induce spanning trees for $$j=1,2,\ldots,s$$. In this paper we study the following question: what is the smallest $m=m(n)$ such that w.h.p. $[m]$ contains a MultiTree. We prove a hitting time result for $s=2$ and an $$O(n\log n)$$ bound for $$s\geq 3$$.more » « less
-
We study the multi-level Steiner tree problem: a generalization of the Steiner tree problem in graphs where terminals T require varying priority, level, or quality of service. In this problem, we seek to find a minimum cost tree containing edges of varying rates such that any two terminals u, v with priorities P(u), P(v) are connected using edges of rate min{P(u),P(v)} or better. The case where edge costs are proportional to their rate is approximable to within a constant factor of the optimal solution. For the more general case of non-proportional costs, this problem is hard to approximate with ratio c log log n, where n is the number of vertices in the graph. A simple greedy algorithm by Charikar et al., however, provides a min{2(ln |T | + 1), lρ}-approximation in this setting, where ρ is an approximation ratio for a heuristic solver for the Steiner tree problem and l is the number of priorities or levels (Byrka et al. give a Steiner tree algorithm with ρ ≈ 1.39, for example). In this paper, we describe a natural generalization to the multi-level case of the classical (single-level) Steiner tree approximation algorithm based on Kruskal’s minimum spanning tree algorithm. We prove that this algorithm achieves an approximation ratio at least as good as Charikar et al., and experimentally performs better with respect to the optimum solution. We develop an integer linear programming formulation to compute an exact solution for the multi-level Steiner tree problem with non-proportional edge costs and use it to evaluate the performance of our algorithm on both random graphs and multi-level instances derived from SteinLib.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
