Given a connected graph and a vertex x ∈ V (G), the geodesic graph Px(G) has the same vertex set as G with edges uv iff either v is on an x − u geodesic path or u is on an x − v geodesic path. A characterization is given of those graphs all of whose geodesic graphs are complete bipartite. It is also shown that the geodetic number of the Cartesian product of Km,n with itself, where m, n ≥ 4, is equal to the minimum of m, n and eight.

A positive integer n is said to be Wiener graphical, if there exists a graph G with Wiener index n. In this paper, we prove that any positive integer n(≠ 2,5) is Wiener graphical. For any positive integer p, an interval [a,b] is said to be a p-Wiener interval if for each positive integer n ∈ [a,b] there exists a graph G on p vertices such that W(G) = n. For any positive integer p, an interval [a,b] is said to be p-Wiener free interval (p-hyper-Wiener free interval) if there exist no graph G on p...

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.

Frankl and Rödl [3] proved a strong regularity lemma for 3-uniform hypergraphs, based on the concept of δ-regularity with respect to an underlying 3-partite graph. In applications of that lemma it is often important to be able to "glue" together separate pieces of the desired subhypergraph. With this goal in mind, in this paper it is proved that every pair of typical edges of the underlying graph can be connected by a hyperpath of length at most seven. The typicality of edges is defined in terms...

By a ternary system we mean an ordered pair $(W,R)$, where $W$ is a finite nonempty set and $R\subseteq W\times W\times W$. By a signpost system we mean a ternary system $(W,R)$ satisfying the following conditions for all $x,y,z\in W$: if $(x,y,z)\in R$, then $(y,x,x)\in R$ and $(y,x,z)\notin R$; if $x\ne y$, then there exists $t\in W$ such that $(x,t,y)\in R$. In this paper, a signpost system is used as a common description of a connected graph and a spanning tree of the graph. By a ct-pair we mean an ordered pair $(G,T)$, where $G$ is a connected graph and $T$ is a spanning tree of $G$. If $(G,T)$ is a ct-pair, then by the guide to...