Weighted Cages

Cages [8] have been studied since 1947 when they were introduced by Tutte in [18]. They are regular graphs of a given girth with the smallest number of vertices for the given parameters. In 1963 Sachs [16] proved that for each $k\geq 2$ and each $g\geq 3$ there is a $k$-regular graph of girth $g$ which implies that a cage exists for each such parameters. The smallest integer $n$ for which there is a $k$-regular graph of girth $g$ on $n$ vertices is denoted by $n(k,g)$ and a $k$-regular graph of girth $g$ with $n(k,g)$ vertices is called a $(k,g)$-cage. Several variations of the notion of cage have been studied in the literature including, among others: Biregular cages [1, 9], biregular bipartite cages [4, 11], vertex-transitive cages [14], Cayley cages [10], mixed cages [2, 3, 7] and mixed geodetic cages [17].

Standard terminology on graph theory used here, will be quickly reviewed in the next section.

In this work, we extend the notion of cage to weighted graphs. In general, a weighted graph, is a (simple, finite) graph $G=(V,E)$ together with a weight function $w:E(G)\rightarrow\mathbb{R}$, however, to keep the presentation as simple as possible, we shall focus on weight functions of the form $w:E(G)\rightarrow\{1,2\}$. An edge with weight 1 is called a light edge while one with weight 2 is called a heavy edge.

Under these circumstances, each weighted graph $G$, wgraph for short, may be specified by a couple of graphs $L=L(G)$ and $H=H(G)$, which are the spanning subgraphs of $G$ formed by the light edges and the heavy edges of $G$ (respectively). Hence, we shall represent a wgraph $G$ by $G=(L,H)$, where $L$ and $H$ are graphs such that $V(L)=V(H)$ and $E(L)\cap E(H)=\varnothing$.

In order to maintain the regularity aspect of the original notion we require $L$ and $H$ to be regular. Thus an $(a,b)$-regular wgraph is a wgraph $G=(L,H)$ where $L$ is $a$-regular and $H$ is $b$-regular. A wcycle in $G$ is a cycle whose edges may be light or heavy and its weight is the sum of the weights of the edges composing it. The girth of a wgraph $G$ is the minimum weight of its wcycles. Finally, by analogy with cages, we may define an $(a,b,g)$-wgraph as an $(a,b)$-regular wgraph of girth $g$, and an $(a,b,g)$-wcage as an $(a,b,g)$-wgraph of minimum order. We shall represent the order of an $(a,b,g)$-wcage by $n(a,b,g)$.

In this paper, we characterize their existence and, for the cases $g=3,4$, we determine the value of $n(a,b,g)$; We also determine $n(a,b,g)$ for $a=1,2$ when $g=5,6$. We give Moore-like bounds and present some computational results.

An interesting feature of weighted cages is that, contrary to what happens with ordinary cages, $n(a,b,g)$ is not always monotone increasing in all its parameters, since we shall see that $n(3,1,4)=8>6=n(3,2,4)$ in Section 6 and that $n(4,1,5)=20>19=n(4,2,5)$ in Section 8.

We note that many of our results may be readily extended to weights of the form $w:E(G)\rightarrow\{w_{1},w_{2}\}\subset\mathbb{N}$.

Our graphs are simple and finite. We use standard terminology for denoting the set of vertices and the set of edges of a graph $X$: $X=(V,E)$, $V=V(X)$ and $E=E(X)$. The order of a graph $X$ is $|X|=|V(X)|$. An edge is an unordered pair of vertices $\{x,y\}$, which we may also write as $xy$. We write $x\simeq_{X}y$ for the adjacent-or-equal relation on a graph $X$. The degree of a vertex $x$ in $X$ is defined by $deg_{X}(x)=|\{xy:xy\in E(X)\}|$. The maximum degree is $\Delta(X)=\max\{deg_{X}(x):x\in V(X)\}$. A graph $X$ is $r$-regular if $deg(x)=r$, for all vertices $x\in V(X)$. The distance between vertices $x$ and $y$ in $X$ is denoted by $dist_{X}(x,y)$. The complete graphs on $n$ vertices are represented by $K_{n}$ and the complete balanced bipartite graphs on $n$ vertices are denoted by $K_{m,m}$, where $m=\frac{n}{2}$. Given graphs $X$ and $Y$, some standard operations on graphs are: the complement of a graph $\overline{X}=(V(X),\overline{E(X)})$, where $\overline{E(X)}=\{\{x,y\}:x,y\in V(X),x\neq y\textup{ and }\{x,y\}\not\in E(X)\}$, the square of a graph $X^{2}=(V(X),E(X^{2}))$, where $E(X^{2})=\{\{x,y\}:0<dist_{X}(x,y)\leq 2\}$ and the union of graphs $X\cup Y=(V(X)\cup V(Y),E(X)\cup E(Y))$, while the disjoint union is $X\cupdot Y=(V(X)\cupdot V(Y),E(X)\cupdot E(Y))$. Here we define the difference of graphs as $X-Y=(V(X),E(X)-E(Y)$, that is, the edges of $Y$, are removed from $X$, but not the vertices. The girth $g(X)$ of a graph, $X$, is the length of a shortest cycle in $X$. An $(r,g)$-graph is an $r$-regular graph of girth $g$. An $(r,g)$-cage is an $(r,g)$-graph of minimum order. The order of an $(r,g)$-cage is denoted by $n(r,g)$; when no such cage exists, we define $n(r,g)=\infty$ (this happens exactly when $r<2$ or $g<3$).

A weighted graph (wgraph for short) is $G=(L,H)$, where $L=L(G)$ is the light-subgraph of $G$ and $H=H(G)$ is the heavy-subgraph of $G$; both $L$ and $H$ are ordinary graphs and we require that $V(L)=V(H)$ and $E(L)\cap E(H)=\varnothing$. Light edges have weight 1 and heavy edges have weight 2. A wcycle (wpath) in $G$ is a cycle (path) whose edges may be light or heavy and its weight is the sum of the weights of the edges composing it. The wdistance between two vertices $x$ and $y$ in $G$ is the minimum weight of a wpath in $G$ joining $x$ and $y$. Other terms like wtree and subwgraph will be used with the obvious meaning.

We say that $G=(L,H)$ is $(a,b)$-regular if $L$ is $a$-regular and $H$ is $b$-regular. The girth, $g(G)$, of a wgraph is the minimum weight of a wcycle in $G$. An $(a,b,g)$-wgraph $G$ is an $(a,b)$-regular wgraph $G$ of girth $g$ and an $(a,b,g)$-wcage is an $(a,b,g)$-wgraph of minimum order. We define $n(a,b,g)$ as the order of an $(a,b,g)$-wcage (and we define $n(a,b,g)=\infty$ if there is no such $(a,b,g)$-wcage).

It should be clear that $n(a,b,g)=\infty$ whenever $a+b\leq 1$ or $g<3$. Also, it is immediate that $n(a,0,g)=n(a,g)$ and that $n(0,b,g)=n(b,\frac{g}{2})$ whenever $g$ is even and $g\geq 6$ (otherwise, $n(0,b,g)=\infty$). A $(1,1,g)$-wcage must be a wcycle of weight $g$ with alternating light and heavy edges, and hence:

We shall use congruence module 2 very often, and hence we shall abbreviate “$x\equiv y\mod 2$” simply as “$x\equiv y$”. It is a well know result (sometimes called the first theorem of graph theory or the degree-sum formula) that the sum of the degrees of a graph is even (and equals twice the number of edges). For an $r$-regular graph of order $n$, this means $nr\equiv 0$, and hence that there are no odd-regular graphs of odd order. This fact will be used very often in this paper and we shall refer to it simply as “parity forbids”, as in: “parity forbids $r=3$ and $n=7$”. We shall often need the following four lemmas:

Recall that a $k$-factor, $F$, of a graph $X$ is a $k$-regular spanning subgraph of $X$. Thus a $1$-factor is a perfect matching and a $2$-factor is a collection of cycles that span all of $X$. A $k$-factorization of $X$ is a decomposition of $X$ into $k$-factors, that is, a collection of $k$-factors $\{F_{i}\}_{i\in I}$, such that $E(F_{i})\cap E(F_{j})=\varnothing$ for all $i\neq j$ and $G=\bigcup_{i\in I}F_{i}$.

Given two graphs $Z$, $Y$, a (weak) morphism, $\varphi:Z\rightarrow Y$, is a function $\varphi:V(Z)\rightarrow V(Y)$, such that $z\simeq_{Z}z^{\prime}$ implies $\varphi(z)\simeq_{Y}\varphi(z^{\prime})$. Note that $\varphi$ may map adjacent vertices into equal vertices. For $zz^{\prime}\in E(Z)$ we define $\varphi(zz^{\prime})=\{\varphi(z),\varphi(z^{\prime})\}$ which may be singleton or an edge in $Y$. We also define $\varphi^{-1}(y)=\{z\in V(Z):\varphi(z)=y\}$ and $\varphi^{-1}(yy^{\prime})=\{zz^{\prime}\in E(Z):\varphi(zz^{\prime})=yy^{\prime}\}$.

Recall that a wcycle is a cycle composed by light and heavy edges and that its weight is the sum of the weights of its edges. An $(a,b,g)$-wcycle is a wcycle $C=(L,H)$ of weight $g$ such that, for each $x\in V(C)$, $deg_{L}(x)\leq a$ and $deg_{H}(x)\leq b$. Hence, if $C$ is an $(a,b,g)$-wcycle, then it is also an $(a^{\prime},b^{\prime},g)$-wcycle, whenever $a^{\prime}\geq a$ and $b^{\prime}\geq b$. For instance, a cycle of length $g$ composed only of light edges is an $(a,0,g)$-wcycle, for each $a\geq 2$. Similarly, a cycle of length $\ell$ composed only of heavy edges is a $(0,b,2\ell)$-wcycle, for each $b\geq 2$. Also, any wcycle of weight $g$ is a $(2,2,g)$-wcycle, but there are no $(a,b,g)$-wcycles when $a+b\leq 1$. Note that any $(a,b,g)$-wcage contains at least one $(a,b,g)$-wcycle.

We shall prove in this section that an $(a,b,g)$-wcage exists whenever an $(a,b,g)$-wcycle exists. The idea is very simple: Start by taking such an $(a,b,g)$-wcycle, extend it to achieve the light-regularity and then extend it again to achieve the heavy-regularity. The formal details, however, require a series of lemmas. Let us begin by characterizing the existence of $(a,b,g)$-wcycles:

Note that, given $Z=X\rtimes_{\varphi}Y$, we must have that $\varphi$ is vertex- and edge-surjective, that $|Z|=|X||Y|$, and that $Z$ is the disjoint union of $|Y|$ copies of $X$ with some additional external edges, which only connect vertices from different copies of $X$ in $Z$ and such that given two such copies $X_{1}$ and $X_{2}$ of $X$ in $Z$, there is at most one external edge connecting a vertex from $X_{1}$ to a vertex from $X_{2}$.

The general construction in the previous theorem gives bad general upper bounds. In several cases, we can get better upper bounds using the same ideas as shown in the Theorem 3.5.

The order of an $(r,g)$-cage, $n(r,g)$, is finite for $r\geq 2$ and $g\geq 3$, but for the constructions used in Theorem 3.5 we shall need this variant, $\tilde{n}(r,g)$, of $n(r,g)$ which is finite for $r\geq 0$, $g\geq 2$:

This function, $\tilde{n}(r,g)$, is the order of the smallest $r$-regular graph $X$ of girth $g(X)\geq g$. It coincides with $n(r,g)$ when an $(r,g)$-cage exists (i.e. when $r\geq 2$ and $g\geq 3$), otherwise $X$ is a complete graph on $r+1$ vertices and the girth of $X$ is either $\infty$ (no cycles) or $3$.

Much in the way of Moore’s lower bounds for cages [13], we may also provide lower bounds for wcages. As in the classic case, we construct a wtree which must be an induced subwgraph of any wcage of some given parameters, and where all the vertices must be different to avoid creating wcycles of weight less than $g$. The result is Theorem 4.1 and this section is devoted to prove it.

Assume first that $g$ is odd. Start with a root vertex and create a wtree of depth (wdistance from the root) $h=\lfloor(g-1)/2\rfloor=(g-1)/2$ whose inner vertices have $a$ and $b$ light incident edges and heavy incident edges, respectively. All of these vertices must be different since, otherwise we would form a wcycle of weight at most $2h=g-1<g$, which are forbidden. Any $(a,b,g)$-wcage must contain this wtree as an induced subwgraph, and hence the order of the wtree is a lower bound for $n(a,b,g)$.

Since we have light and heavy edges, we should create the several levels of the wtree, considering the wdistance of the vertices from the root (the root is at level 0), and hence heavy edges skip two levels at a time as in Figure 2. We shall consider two kinds of vertices, the light vertices (in green) and the heavy vertices (in red): Vertices are light or heavy depending on the weight of the edge connecting them to their respective parents. The root vertex is not of any of these kinds, but we shall see that, for counting purposes, it can be considered light or heavy depending on the case at hand.

We define $L_{i}$ as the number of light vertices at level $i$ and $H_{i}$ as the number of heavy vertices at level $i$. Then it should be clear that the recurrences for light and heavy vertices at level $i$ are:

And that, the base cases are:

Note that in this case the root vertex is considered light ($L_{0}=1$), since it affects the number of heavy vertices at level 2 according to the recurrence for $H_{i}$ in (2), but it does not affect the light vertices at level 1 since those are determined by the base cases in (3) and not by the recurrences.

For future reference, let us name this lower bound.

Now assume $g$ is even. As before we can construct a wtree, and again, its depth must be at most $h=\lfloor(g-1)/2\rfloor=(g-2)/2$ to guarantee that all of the vertices are different (assuming there are no wcycles of weight less than $g$). Although we can not add an additional full level preserving this guarantee, we can indeed add an additional level but only to the subwtree of one of the children of the root and still guarantee that all the vertices are different, this is true since $h+(h+1)=(g-2)/2+(g-2)/2+1=g-1<g$. Since we have light and heavy edges, this can be done in two different ways as shown in figures 3(a) and 3(b). There, the child of the root selected to have an additional level of descendants is marked with a square box. Any $(a,b,g)$-wcage must contain both of these wtrees as induced subwgraphs and hence the orders of these wtrees are both lower bounds for $n(a,b,g)$.