For a finite simple graph $G$ of positive order, let $s_k(G)$ be the number of its $k$-vertex tree subgraphs. We prove that, among graphs of a fixed order $n$, the ratios $s_k(G)/s_k(K_n)$ form a nonincreasing sequence in $k$. It follows that the complete graph maximizes the mean subtree order: $\mu(G)\leq\mu(K_n)$, with equality if and only if $G$ is complete. This monotonicity theorem also establishes the $s_{n-1}$-to-$s_n$ ratio conjecture posed in recent work on extremal mean subtree order. The proof lifts a known coupling of rooted Cayley-tree shapes of consecutive orders to uniform labeled tree subgraphs of $K_n$ that are nested at every sample point. Event inclusion gives the count inequalities, and a double-sum identity gives the mean bound.
For a finite simple graph $G$ and an integer $k\ge0$, let $w_k(G)$ denote the number of walks of length $k$. We prove the conjecture of T\"aubig, Weihmann, Kosub, Hemmecke, and Mayr for every finite tree and determine all equality cases. If $T$ has $n\ge1$ vertices, then $n w_{k+1}(T)-2(n-1)w_k(T)\ge0$ for every $k\ge1...
Dong-Xiu Cai, Zhen-Bo Chen, Jia-Sheng Zeng et al.· 0 citations
We prove that the number of labelled embeddings of any $n$-vertex tree $T$ into an $n$-vertex graph $G$ of maximum degree $d$ satisfies $$ \mathrm{inj}(T,G) \leq (d/e)^n \exp(o_d(1) n). $$ The bound is sharp up to determining $o_d(1)$, even for paths, and the dependence of the error $\exp(o_d(1)n)$ on $d$ is necessary....
Csongor Beke, V. Boskovic, Nina Kamčev et al.· 0 citations
A finite connected graph is rarely a Cayley graph. We measure how far it is from being one: given $G$ with $n$ vertices and $m$ edges, how few edges must be added, or added and deleted, before the result is a Cayley graph of an abelian group of order $n$ on the same vertex set? This defines two invariants, the completi...
For a positive integer $k$, let $\beta_k(G)$ be the maximum cardinality of a vertex set inducing maximum degree less than $k$, and let $SF_k(G)$ be the maximum cardinality of a minimal $k$-star-forming set. The known inequality $\beta_k(G)\le SF_k(G)$ suggests asking when equality holds. We place this question in the f...
For an $F$-free graph $G$, a non-edge is $F$-saturating if adding it to $G$ creates a copy of $F$. We denote by $f_{p+1}(n,m)$ the minimum number of $K_{p+1}$-saturating non-edges in a $K_{p+1}$-free $n$-vertex graph with $m$ edges. Erd\H{o}s and Tuza conjectured that $f_4\left(n,\mathrm{ex}(n,K_3)+ 1\right)= (1 + o(1)...
For $n\ge6$, $m=\binom n2$, let the complete-graph incidence family on $K_n$ have the vertices of $K_n$ as columns, its edges as rows, and the incidence graph as one-edge graph. The universal cell bound of L\"ofberg and Qi gives $z_2(m,n)\le Z(n):=\lfloor n(n-1)(n+2)/4\rfloor$. We implement the nested one-factorization...
Yan-Nan Chen, J. Löfberg, Li-Qun Qi· 2 citations· ⚡1
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
