The $P_3$ intersection graph of a graph $G$ has for vertices all the induced paths of order 3 in $G$. Two vertices in $P_3\left(G\right)$ are adjacent if the corresponding paths in $G$ are not disjoint. A $w$-container between two different vertices $u$ and $v$ in a graph $G$ is a set of $w$ internally vertex disjoint paths between $u$ and $v$. The length of a container is the length of the longest path in it. The $w$-wide diameter of $G$ is the minimum number $l$ such that there is a $w$-container of length at most $l$ between any pair...

A homomorphism of an oriented graph $G=(V,A)$ to an oriented graph $G^{\text{'}}=(V^{\text{'}},A^{\text{'}})$ is a mapping $\varphi$ from $V$ to $V^{\text{'}}$ such that $\varphi \left(u\right)\varphi \left(v\right)$ is an arc in $G^{\text{'}}$ whenever $uv$ is an arc in $G$. A homomorphism of $G$ to $G^{\text{'}}$ is said to be $T$-preserving for some oriented graph $T$ if for every connected subgraph $H$ of $G$ isomorphic to a subgraph of $T$, $H$ is isomorphic to its homomorphic image in $G^{\text{'}}$. The $T$-preserving oriented chromatic number ${\overrightarrow{\chi }}_T\left(G\right)$ of an oriented graph $G$ is the minimum number of vertices in an oriented graph $G^{\text{'}}$ such that there exists a $T$-preserving...

Let $D$ be an oriented graph of order $n$ and size $m$. A $\gamma$-labeling of $D$ is a one-to-one function $fV\left(D\right)\to \{0,1,2,...,m\}$ that induces a labeling $f^{\text{'}}E\left(D\right)\to \{\pm 1,\pm 2,...,\pm m\}$ of the arcs of $D$ defined by $f^{\text{'}}\left(e\right)=f\left(v\right)-f\left(u\right)$ for each arc $e=(u,v)$ of $D$. The value of a $\gamma$-labeling $f$ is $\mathrm{v}al\left(f\right)={\sum }_{e\in E\left(G\right)}{f}^{\text{'}}\left(e\right).$ A $\gamma$-labeling of $D$ is balanced if the value of $f$ is 0. An oriented graph $D$ is balanced if $D$ has a balanced labeling. A graph $G$ is orientably balanced if $G$ has a balanced orientation. It is shown that a connected graph $G$ of order $n\ge 2$ is orientably balanced unless $G$ is a tree, $n\equiv 2\left(mod4\right)$, and every...

As introduced by F. Harary in 1994, a graph $G$ is said to be an $integral$ $sum$ $graph$ if its vertices can be given a labeling $f$ with distinct integers so that for any two distinct vertices $u$ and $v$ of $G$, $uv$ is an edge of $G$ if and only if $f\left(u\right)+f\left(v\right)=f\left(w\right)$ for some vertex $w$ in $G$. We prove that every integral sum graph with a saturated vertex, except the complete graph $K_3$, has edge-chromatic number equal to its maximum degree. (A vertex of a graph $G$ is said to be if it is adjacent to every...