التفاصيل البيبلوغرافية
| العنوان: |
Decreasing the mean subtree order by adding k edges. |
| المؤلفون: |
Cambie, Stijn, Chen, Guantao, Hao, Yanli, Tokar, Nizamettin |
| المصدر: |
Journal of Graph Theory; Mar2024, Vol. 105 Issue 3, p357-366, 10p |
| مصطلحات موضوعية: |
GRAPH connectivity, LOGICAL prediction |
| مستخلص: |
The mean subtree order of a given graph G $G$, denoted μ(G) $\mu (G)$, is the average number of vertices in a subtree of G $G$. Let G $G$ be a connected graph. Chin et al. conjectured that if H $H$ is a proper spanning supergraph of G $G$, then μ(H)>μ(G) $\mu (H)\gt \mu (G)$. Cameron and Mol disproved this conjecture by showing that there are infinitely many pairs of graphs H $H$ and G $G$ with H⊃G $H\supset G$, V(H)=V(G) $V(H)=V(G)$ and |E(H)|=|E(G)|+1 $|E(H)|=|E(G)|+1$ such that μ(H)<μ(G) $\mu (H)\lt \mu (G)$. They also conjectured that for every positive integer k $k$, there exists a pair of graphs G $G$ and H $H$ with H⊃G $H\supset G$, V(H)=V(G) $V(H)=V(G)$, and |E(H)|=|E(G)|+k $|E(H)|=|E(G)|+k$ such that μ(H)<μ(G) $\mu (H)\lt \mu (G)$. Furthermore, they proposed that μ(Km+nK1)<μ(Km,n) $\mu ({K}_{m}+n{K}_{1})\lt \mu ({K}_{m,n})$ provided n≫m $n\gg m$. In this note, we confirm these two conjectures. [ABSTRACT FROM AUTHOR] |
|
Copyright of Journal of Graph Theory is the property of Wiley-Blackwell and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| قاعدة البيانات: |
Complementary Index |
