Some upper bounds for the $3$-proper index of graphs

Abstract

A tree $T$ in an edge-colored graph is a {\it proper tree} if no two adjacent edges of $T$ receive the same color. Let $G$ be a connected graph of order $n$ and $k$ be a fixed integer with $2\le k\le n$. For a vertex subset $S\subseteq V(G)$ with $\left|S\right|\ge 2$, a tree containing all the vertices of $S$ in $G$ is called an $S$-tree. An edge-coloring of $G$ is called a \emph{$k$-proper coloring} if for every $k$-subset $S$ of $V(G)$, there exists a proper $S$-tree in $G$. For a connected graph $G$, the \emph{$k$-proper index} of $G$, denoted by $p{x}_k(G)$, is the smallest number of colors that are needed in a $k$-proper coloring of $G$. In this paper, we show that for every connected graph $G$ of order $n$ and minimum degree $\delta \ge 3$, $p{x}_3(G)\le n\frac{\ln (\delta +1)}{\delta +1}(1+o_{\delta }(1))+2$. We also prove that for every connected graph $G$ with minimum degree at least $3$, $p{x}_3(G)\le p{x}_3(G[D])+3$ when $D$ is a connected $3$-way dominating set of $G$ and $p{x}_3(G)\le p{x}_3(G[D])+1$ when $D$ is a connected $3$-dominating set of $G$. In addition, we obtain tight upper bounds of the 3-proper index for two special graph classes: threshold graphs and chain graphs. Finally, we prove that $p{x}_3(G)\le \lfloor \frac{n}{2}\rfloor$ for any 2-connected graphs with at least four vertices.

arXiv comment18 pages

References in corpus (1)

• A Mixed-effects Model for Incomplete Data With Batch-Level Abundance-Dependent Missing-Data Mechanism

Cited by in corpus (1)

• The $(k,\ell )$-proper index of graphs