We show that the out-radius and the radius grow linearly, or "almost" linearly, in iterated line digraphs. Further, iterated line digraphs with a prescribed out-center, or a center, are constructed. It is shown that not every line digraph is admissible as an out-center of line digraph.

A radio antipodal coloring of a connected graph $G$ with diameter $d$ is an assignment of positive integers to the vertices of $G$, with $x\in V\left(G\right)$ assigned $c\left(x\right)$, such that $$d(u,v)+\left|c\right(u)-c(v\left)\right|\ge d$$ for every two distinct vertices $u$, $v$ of $G$, where $d(u,v)$ is the distance between $u$ and $v$ in $G$. The radio antipodal coloring number $\mathrm{a}c\left(c\right)$ of a radio antipodal coloring $c$ of $G$ is the maximum color assigned to a vertex of $G$. The radio antipodal chromatic number $\mathrm{a}c\left(G\right)$ of $G$ is $min\left\{\mathrm{a}c\right(c\left)\right\}$ over all radio antipodal colorings $c$ of $G$. Radio antipodal chromatic numbers of paths...

For a connected graph G of diameter d and an integer k with 1 ≤ k ≤ d, a radio k-coloring of G is an assignment c of colors (positive integers) to the vertices of G such that d(u,v) + |c(u)- c(v)| ≥ 1 + k for every two distinct vertices u and v of G, where d(u,v) is the distance between u and v. The value rcₖ(c) of a radio k-coloring c of G is the maximum color assigned to a vertex of G. The radio k-chromatic number rcₖ(G) of G is the minimum value of rcₖ(c) taken over all radio k-colorings c of...

The eccentricity $e\left(v\right)$ of a vertex $v$ is defined as the distance to a farthest vertex from $v$. The radius of a graph $G$ is defined as a $r\left(G\right)={min}_{u\in V\left(G\right)}\left\{e\left(u\right)\right\}$. A graph $G$ is radius-edge-invariant if $r(G-e)=r\left(G\right)$ for every $e\in E\left(G\right)$, radius-vertex-invariant if $r(G-v)=r\left(G\right)$ for every $v\in V\left(G\right)$ and radius-adding-invariant if $r(G+e)=r\left(G\right)$ for every $e\in E\left(\overline{G}\right)$. Such classes of graphs are studied in this paper.

On étudie à l'aide du système AutoGraphiX 2 (AGX 2) des relations de la forme $${\underline{b}}_n\le g\oplus i\le {\overline{b}}_n$$ où g désigne la maille d'un graphe G=(V, E), i un autre invariant parmi la distance moyenne $\overline{l}$, l'index λ1, l'indice de Randić R et le nombre de domination β, $\oplus$ désigne l'une des opérations +, -, ×, /, ${\underline{b}}_n$ et ${\overline{b}}_n$ des fonctions de l'ordre n du graphe qui bornent l'expression $g\oplus i$ et sont atteintes pour tout n (sauf éventuellement de très petites valeurs du fait des effets de bord). Les résultats prouvés ou discutés ci-dessous...

In this paper we compute some bounds of the Balaban index and then by means of group action we compute the Balaban index of vertex transitive graphs. ACM Computing Classification System (1998): G.2.2 , F.2.2.

For an ordered set $W=\{w_1,w_2,\cdots ,w_k\}$ of vertices and a vertex $v$ in a connected graph $G$, the (metric) representation of $v$ with respect to $W$ is the $k$-vector $r\left(v\right|W)=(d(v,w_1),d(v,w_2),\cdots ,d(v,w_k))$, where $d(x,y)$ represents the distance between the vertices $x$ and $y$. The set $W$ is a resolving set for $G$ if distinct vertices of $G$ have distinct representations with respect to $W$. A resolving set of minimum cardinality is called a minimum resolving set or a basis and the cardinality of a basis for $G$ is its dimension $dimG$. A set $S$ of vertices in $G$ is a dominating set...

A directed Cayley graph $C(\Gamma ,X)$ is specified by a group $\Gamma$ and an identity-free generating set $X$ for this group. Vertices of $C(\Gamma ,X)$ are elements of $\Gamma$ and there is a directed edge from the vertex $u$ to the vertex $v$ in $C(\Gamma ,X)$ if and only if there is a generator $x\in X$ such that $ux=v$. We study graphs $C(\Gamma ,X)$ for the direct product $Z_m\times Z_n$ of two cyclic groups $Z_m$ and $Z_n$, and the generating set $X=\left\{\right(0,1),(1,0),(2,0),\cdots ,(p,0\left)\right\}$. We present resolving sets which yield upper bounds on the metric dimension of these graphs for $p=2$ and $3$.

For any nontrivial connected graph $F$ and any graph $G$, the $F$-degree of a vertex $v$ in $G$ is the number of copies of $F$ in $G$ containing $v$. $G$ is called $F$-continuous if and only if the $F$-degrees of any two adjacent vertices in $G$ differ by at most 1; $G$ is $F$-regular if the $F$-degrees of all vertices in $G$ are the same. This paper classifies all $P_4$-continuous graphs with girth greater than 3. We show that for any nontrivial connected graph $F$ other than the star $K_{1,k}$, $k\ge 1$, there exists a regular graph that is not...

A graph H is obtained from a graph G by an edge rotation if G contains three distinct vertices u,v, and w such that uv ∈ E(G), uw ∉ E(G), and H = G-uv+uw. A graph H is obtained from a graph G by an edge jump if G contains four distinct vertices u,v,w, and x such that uv ∈ E(G), wx∉ E(G), and H = G-uv+wx. If a graph H is obtained from a graph G by a sequence of edge jumps, then G is said to be j-transformed into H. It is shown that for every two graphs G and H of the same order (at least 5) and same...

The concept of a route system was introduced by the present author in [3].Route systems of a connected graph $G$ generalize the set of all shortest paths in $G$. In this paper some properties of route systems are studied.

The well known types of routes in graphs and directed graphs, such as walks, trails, paths, and induced paths, are characterized using axioms on vertex sequences. Thus non-graphic characterizations of the various types of routes are obtained.