论文标题
具有给定独立号码的图的最佳适当连接号
The optimal proper connection number of a graph with given independence number
论文作者
论文摘要
如果每对不同的顶点之间存在一个路径，则可以正确连接边缘色的连接图$ G $，则存在一条路径，没有两个相邻的边缘具有相同的颜色。 Fujita（2019）引入了最佳的正确连接号码$ {\ MathRM {pc} _ {\ Mathrm {opt}}}}}}}（g）$ for单色连接的图形$ g $，以使连接的图形正确地连接有效地连接。更准确地说，$ {\ mathrm {pc} _ {\ mathrm {opt}}}}}（g）$是最小的整数$ p+q $，当一个人通过重新连接的$ p $ edges添加了$ q $ c $ q $ c $ p $ p $。 在本文中，我们表明$ {\ mathrm {pc} _ {\ mathrm {opt}}}}}（g）$在独立数$α（g）$方面具有上限。也就是说，我们证明，对于连接的图形$ g $，$ {\ mathrm {pc} _ {\ mathrm {opt}}}}}}}}}}（g）\ le \ frac {5α（g）-1} -1} -1} {2} $。 MoreOevr，对于$α（g）\ leq 3 $的情况，我们将上限提高到$ 4 $，这很紧。
An edge-colored connected graph $G$ is properly connected if between every pair of distinct vertices, there exists a path that no two adjacent edges have a same color. Fujita (2019) introduced the optimal proper connection number ${\mathrm{pc}_{\mathrm{opt}}}(G)$ for a monochromatic connected graph $G$, to make a connected graph properly connected efficiently. More precisely, ${\mathrm{pc}_{\mathrm{opt}}}(G)$ is the smallest integer $p+q$ when one converts a given monochromatic graph $G$ into a properly connected graph by recoloring $p$ edges with $q$ colors. In this paper, we show that ${\mathrm{pc}_{\mathrm{opt}}}(G)$ has an upper bound in terms of the independence number $α(G)$. Namely, we prove that for a connected graph $G$, ${\mathrm{pc}_{\mathrm{opt}}}(G)\le \frac{5α(G)-1}{2}$. Moreoevr, for the case $α(G)\leq 3$, we improve the upper bound to $4$, which is tight.
