The k-proper index of graphs

DOI10.1016/J.AMC.2016.10.025MaRDI QIDQ1734744zbMATH OpenOpenAlexFDO

Authors Lin Chen, Jin-Feng Liu, Xueliang Li

Publication date 27 March 2019

Published in Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1601.03503

zbMATH Keywords

\(k\)-proper indexcharacterization of graphscoloring of graphs

Mathematics Subject Classification ID

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

Abstract: A tree $T$ in an edge-colored graph is a emph{proper tree} if any two adjacent edges of $T$ are colored with different colors. Let $G$ be a graph of order $n$ and $k$ be a fixed integer with $2leqkleqn$. For a vertex set $SsubseteqV(G)$, a tree containing the vertices of $S$ in $G$ is called an emph{$S$-tree}. An edge-coloring of $G$ is called a emph{$k$-proper coloring} if for every set $S$ of $k$ vertices in $G$, there exists a proper $S$-tree in $G$. The emph{$k$-proper index} of a nontrivial connected graph $G$, denoted by $p{x}_k(G)$, is the smallest number of colors needed in a $k$-proper coloring of $G$. In this paper, some simple observations about $p{x}_k(G)$ for a nontrivial connected graph $G$ are stated. Meanwhile, the $k$-proper indices of some special graphs are determined, and for every pair of positive integers $a$, $b$ with $2leqaleqb$, a connected graph $G$ with $p{x}_k(G)=a$ and $r{x}_k(G)=b$ is constructed for each integer $k$ with $3leqkleqn$. Also, the graphs with $k$-proper index $n-1$ and $n-2$ are respectively characterized.

Recommendations

• The \((k,\ell )\)-proper index of graphs
• The \(k\)-Szeged index of graphs
• The k-proper index of complete bipartite and complete multipartite graphs
• The K.Banhatti indices of certain graphs
• Kirchhoff index of graphs and some graph operations
• The Kirchhoff index of subdivisions of graphs
• scientific article; zbMATH DE number 5717210
• Some bounds for the Kirchhoff index of graphs
• On the Graovac-Ghorbani index of graphs
• On the Graovac-Ghorbani index of graphs

Cites work

• A solution to a conjecture on two rainbow connection numbers of a graph.
• Characterizations of graphs having large proper connection numbers
• Graph theory
• Graphs with 3-rainbow index \(n-1\) and \(n-2\)
• Graphs with 4-rainbow index 3 and \(n-1\)
• Hardness and Algorithms for Rainbow Connectivity
• Note on the complexity of deciding the rainbow (vertex-) connectedness for bipartite graphs
• Note on the hardness of rainbow connections for planar and line graphs
• Note on the upper bound of the rainbow index of a graph
• On proper-path colorings in graphs
• On rainbow connection
• Proper connection number and connected dominating sets
• Proper connection number of random graphs
• Proper connection of graphs
• Proper connection with many colors
• Rainbow connection in graphs
• Rainbow trees in graphs and generalized connectivity
• Some upper bounds for 3-rainbow index of graphs
• The (strong) rainbow connection numbers of Cayley graphs on abelian groups
• The 3-rainbow index and connected dominating sets
• The 3-rainbow index of a graph
• The rainbow connection of a graph is (at most) reciprocal to its minimum degree

Cited in

(11)

• Some upper bounds for the 3-proper index of graphs
• The Kirchhoff index of subdivisions of graphs
• Integer indices and spectral properties for the KK_n^j graphs
• Topological indices of the bipartite Kneser graph Hn,k
• scientific article; zbMATH DE number 5942974 (Why is no real title available?)
• scientific article; zbMATH DE number 5717210 (Why is no real title available?)
• scientific article; zbMATH DE number 5631826 (Why is no real title available?)
• scientific article; zbMATH DE number 6921389 (Why is no real title available?)
• The k-proper index of complete bipartite and complete multipartite graphs
• The F–Index for some Special Graphs and some Properties of the F–Index
• The \((k,\ell )\)-proper index of graphs

This page was built for publication: The \(k\)-proper index of graphs

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