论文标题
$ K $ -TREE线图的连接性
$k$-tree connectivity of line graphs
论文作者
论文摘要
对于图$ g =（v，e）$和set $ s \ subseteq v（g）大小至少$ 2 $，$ s $ steiner tree $ t $ t $是$ g $的子图，是$ s \ subseteq v（t）$的树。如果$ e（t）\ cap e（t）\ cap e（t'）= \ emptyset $和$ v（t）\ cap v（t）\ cap v（t）= s $（如果$ e（t）\ e（t）\ e（t）\ cap e（t'（t）\ cap e（t'）= \ emberyset $，则两个$ s $ steiner树$ t $ $ t $ $ t $ $ t $ $ t $ $ t $ $ t $ $ t $ t $ $ t $ $ t $ t $ $ t $ t $ $ t $ t $ $ t $ t $ $ t $ t $ $ t $ t $和$ t'令$κ_G（s）$（resp。Up。cy /λ_g（s）$）表示内部分离的最大数量（resp。Edge-disechoint）$ s $ s $ steiner树，$ g $。然后将$ k $ -tree连接$κ__k（g）$（$ k $ -k $ -tree边缘连接性$ g $）的$ g $定义为最低$κ__g（s）$（s）$（s）$（resp。$λ_g（s）$），其中$ s $ s $ s $ ranges yes $ k $ k $ k $ - $ subsubs $ v）在[H. Li，B。Wu，J。Meng，Y. Ma，Steiner树包装号码和树木连接性，离散数学。 341（2018），1945--1951]，作者推测，如果连接的图形$ g $至少具有$ k $ dertices和至少$ k $ edge，则$κ__k（l（g））\ geq Qλ_k（g）$，对于任何$ k \ geq 2 $，where $ k \ geq 2 $，where $ l（g）$ l（g）$ l是$ g $ $ g $。在本文中，我们确认了这个猜想，并证明了界限是锋利的。
For a graph $G=(V,E)$ and a set $S\subseteq V(G)$ of size at least $2$, an $S$-Steiner tree $T$ is a subgraph of $G$ that is a tree with $S\subseteq V(T)$. Two $S$-Steiner trees $T$ and $T'$ are internally disjoint (resp. edge-disjoint) if $E(T)\cap E(T')=\emptyset$ and $V(T)\cap V(T')=S$ (resp. if $E(T)\cap E(T')=\emptyset$). Let $κ_G (S)$ (resp. $λ_G (S)$) denote the maximum number of internally disjoint (resp. edge-disjoint) $S$-Steiner trees in $G$. The $k$-tree connectivity $κ_k(G)$ (resp. $k$-tree edge-connectivity $λ_k(G)$) of $G$ is then defined as the minimum $κ_G (S)$ (resp. $λ_G (S)$), where $S$ ranges over all $k$-subsets of $V(G)$. In [H. Li, B. Wu, J. Meng, Y. Ma, Steiner tree packing number and tree connectivity, Discrete Math. 341(2018), 1945--1951], the authors conjectured that if a connected graph $G$ has at least $k$ vertices and at least $k$ edges, then $κ_k(L(G))\geq λ_k(G)$ for any $k\geq 2$, where $L(G)$ is the line graph of $G$. In this paper, we confirm this conjecture and prove that the bound is sharp.
