Narrow Results

For $k\ge 1$, in a graph $G$ a set of vertices $D$ is a distance $k$-dominating set of $G$ if all vertices in $G$ are within distance $k$ from a vertex in $D$. The distance $k$-domination number, denoted by ${\gamma }_k(G)$, is the smallest cardinality overall distance $k$-dominating sets of $G$. In this paper, we study some distance parameters and the distance $k$-domination in the edge corona product of graphs. Let $G$ and $H$ be two simple graphs. The edge corona product of $G$ and $H$, denoted by $G◇H$, is the graph obtained from $G$ by adding a copy of $H$ for each edge $e$ of $G$ and joining the end-vertices of $e$ to every vertex in its corresponding copy of $H$. First, we prove that the diameter of $G◇H$ is equal to the diameter of the line graph of $G$ plus one. This allows us to show that $\mathrm{\text{diam}}(G)\le \mathrm{\text{diam}}(G◇H)\le \mathrm{\text{diam}}(G)+2$, then we characterize the graphs achieving both bounds. Also, we determine the radius of $G◇H$ in terms of the radius of $G$. Afterward, we focus on the distance $k$-domination of $G◇H$. We show that ${\gamma }_k(G)\le {\gamma }_k(G◇H)\le {\gamma }_{k-1}(G)$. Moreover, we give a criterion for graphs achieving both bounds. Then, we show that ${\gamma }_2(G◇H)={\gamma }_{\mathrm{\text{ve}}}(G)$, where ${\gamma }_{\mathrm{\text{ve}}}(G)$ is the vertex-edge domination number of $G$. Later, for $k\ge 3$, we show that ${\gamma }_{\mathrm{\text{ve}}}(G^k)\le {\gamma }_k(G◇H)\le {\gamma }_{\mathrm{\text{ve}}}(G^{k-1})$, where $G^k$ denotes the $k$th power graph of $G$. Then, we characterize the graphs achieving both of these bounds. Finally, for all $k\ge 1$, we provide ${\gamma }_k(G◇H)$ when $G$ is a complete graph, path, cycle or some other diameter $2$ graph family where $H$ is any graph.

Let $X$ be a finite simple graph. The $2$-distance graph $D_2(X)$ of $X$ is the graph with the same vertex set as $X$ and two vertices are adjacent if and only if their distance in $X$ is exactly $2$. A graph $G$ is a $2$-distance graph if there exists a graph $X$ such that $D_2(X)\cong G$. In this paper, we give three characterizations of $2$-distance graphs, and find all graphs $X$ such that $D_2(X)\cong k{P}_2$ or $K_m\cup K_n$, where $k\ge 2$ is an integer, $P_2$ is the path of order $2$, and $K_m$ is the complete graph of order $m\ge 1$.

The eccentric connectivity index and second Zagreb eccentricity index are well-known graph invariants defined as the sums of contributions dependent on the eccentricities of adjacent vertices over all edges of a connected graph. The coindices of these invariants have recently been proposed by considering analogous contributions from the pairs of non-adjacent vertices. Here, we obtain several lower and upper bounds on the eccentric connectivity coindex and second Zagreb eccentricity coindex in terms of some graph parameters such as order, size, number of non-adjacent vertex pairs, radius, and diameter, and relate these invariants to some well-known graph invariants such as Zagreb indices and coindices, status connectivity indices and coindices, ordinary and multiplicative Zagreb eccentricity indices, Wiener index, degree distance, total eccentricity, eccentric connectivity index, second eccentric connectivity index, and eccentric-distance sum. Moreover, we compute the values of these coindices for two graph constructions, namely, double graphs and extended double graphs.

Let S be a set of vertices of a connected graph G. The Steiner distance of S is the minimum size among all connected subgraphs of G containing the vertices of S. The sum of all Steiner distances on sets of size k is called the Steiner k-Wiener index. We obtain formulae for bounds on the Steiner–Wiener index of graphs in terms of chromatic number, vertex connectivity and independence number. Also, we obtain bounds for 4-cycle free graphs.

In this paper, we investigate the configuration space ${{𝒮}}_{G,b,\ell }$ associated with the movement of a robotic arm of length $\ell$ on a grid over an underlying graph $G$, anchored at a vertex $b\in G$. We study an associated poset with inconsistent pairs (PIP) ${IP}_{G,b,\ell }$ consisting of indexed paths on $G$. This PIP acts as a combinatorial model for the robotic arm, and we use ${\mathrm{\text{IP}}}_{G,b,\ell }$ to show that the space ${{𝒮}}_{G,b,\ell }$ is a CAT(0) cubical complex, generalizing work of Ardila, Bastidas, Ceballos, and Guo. This establishes that geodesics exist within the configuration space, and yields explicit algorithms for moving the robotic arm between different configurations in an optimal fashion. We also give a tight bound on the diameter of the robotic arm transition graph — the maximal number of moves necessary to change from one configuration to another — and compute this diameter for a large family of underlying graphs $G$.