The k-proper index of complete bipartite and complete multipartite graphs

MaRDI QIDQ4595232zbMATH OpenFDO

Authors Jingshu Zhang, Wenjing Li, Xueliang Li

Publication date 29 November 2017

Full work available at URL https://arxiv.org/abs/1608.00105, http://ajc.maths.uq.edu.au/pdf/68/ajc_v68_p304.pdf

zbMATH Keywords

edge-colored graphproper tree

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15)

Abstract: Let $G$ be a nontrivial connected graph of order $n$ with an edge-coloring $c:E(G)ightarrow1,2,dots,t$,$tinmathbbN$, where adjacent edges may be colored with the same color. A tree $T$ in $G$ is a emph{proper tree} if no two adjacent edges of it are assigned the same color. Let $k$ be a fixed integer with $2leqkleqn$. For a vertex subset $SsubseteqV(G)$ with $|S|geq2$, a tree is called an emph{$S$-tree} if it connects $S$ in $G$ . A emph{$k$-proper coloring} of $G$ is an edge-coloring of $G$ having the property that for every set $S$ of $k$ vertices of $G$, there exists a proper $S$-tree $T$ in $G$. The minimum number of colors that are needed in a $k$-proper coloring of $G$ is defined as the emph{$k$-proper index} of $G$, denoted by $p{x}_k(G)$. In this paper, we determine the 3-proper index of all complete bipartite and complete multipartite graphs and partially determine the $k$-proper index of them for $kgeq4$.

Recommendations

• The \(k\)-proper index of graphs
• The \((k,\ell )\)-proper index of graphs
• The \((k,\ell)\)-rainbow index for complete bipartite and multipartite graphs
• Kirchhoff index and degree Kirchhoff index of complete multipartite graphs
• On the Kirchhoff index of the complement of a bipartite graph
• The IC-indices of complete bipartite graphs
• Bounds for proper \(k\)-connectivity of complete bipartite graphs
• scientific article; zbMATH DE number 5717210
• \(k\)-number of complete muti-partite graphs
• The IC-indices of complete multipartite graphs

Cited in

(7)

• The IC-indices of complete bipartite graphs
• The \(k\)-proper index of graphs
• Some upper bounds for the 3-proper index of graphs
• Color-induced graph colorings
• The \((k,\ell )\)-proper index of graphs
• scientific article; zbMATH DE number 5717210 (Why is no real title available?)
• Topological indices of the bipartite Kneser graph Hn,k

This page was built for publication: The $k$-proper index of complete bipartite and complete multipartite graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4595232)