Yunfang Tang

The star chromatic index of a graph $G$, denoted by $χ'_{st}(G) $, is the minimum number of colors needed to properly color the edges of $G$ such that no path or cycle of length four is bi-colored. Casselgren et al. and Hou et al. independently proved that the star chromatic index of a cubic Halin graph, except a special graph, is at most $6$. It remains an open problem to determine which of such graphs have star chromatic index $5$. In this paper, we show that if $G\ne N_{e_2}$ is a cubic Halin graph whose tree is a caterpillar or a complete tree, then $χ'_{st}(G)=5$.

The \emph{eccentricity} of a vertex $u$ in a graph $G$, denoted by $e_G(u)$, is the maximum distance from $u$ to other vertices in $G$. We study extremal problems for the average eccentricity and the first and second Zagreb eccentricity indices, denoted by $σ_0(G)$, $σ_1(G)$, and $σ_2(G)$, respectively. These are defined by $σ_0(G)=\frac{1}{|V(G)|}\sum_{u\in V(G)}e_G(u)$, $σ_1(G)=\sum_{u\in V(G)}e_G^2(u)$, and $σ_2(G)=\sum_{uv\in E(G)}e_G(u)e_G(v)$. We study lower and upper bounds on these parameters among $n$-vertex connected graphs with fixed diameter, chromatic number, clique number, or matching number. Most of the bounds are sharp, with the corresponding extremal graphs characterized.