For a nontrivial connected graph $F$, the $F$-degree of a vertex $v$ in a graph $G$ is the number of copies of $F$ in $G$ containing $v$. A graph $G$ is $F$-continuous (or $F$-degree continuous) if the $F$-degrees of every two adjacent vertices of $G$ differ by at most 1. All $P_3$-continuous graphs are determined. It is observed that if $G$ is a nontrivial connected graph that is $F$-continuous for all nontrivial connected graphs $F$, then either $G$ is regular or $G$ is a path. In the case of a 2-connected graph $F$, however, there always exists a regular graph that is not $F$-continuous. It is also shown that for every graph $H$ and every 2-connected graph $F$, there exists an $F$-continuous graph $G$ containing $H$ as an induced subgraph.
A graph $G$ is stratified if its vertex set is partitioned into classes, called strata. If there are $k$ strata, then $G$ is $k$-stratified. These graphs were introduced to study problems in VLSI design. The strata in a stratified graph are also referred to as color classes. For a color $X$ in a stratified graph $G$, the $X$-eccentricity $e_X(v)$ of a vertex $v$ of $G$ is the distance between $v$ and an $X$-colored vertex furthest from $v$. The minimum $X$-eccentricity among the vertices of $G$ is the $X$-radius $\mathop {\mathrm rad}\nolimits _XG$ of $G$ and the maximum $X$-eccentricity is the $X$-diameter $\mathop {\mathrm diam}\nolimits _XG$. It is shown that for every three positive integers $a, b$ and $k$ with $a \le b$, there exist a $k$-stratified graph $G$ with $\mathop {\mathrm rad}\nolimits _XG=a$ and $\mathop {\mathrm diam}\nolimits _XG=b$. The number $s_X$ denotes the minimum $X$-eccetricity among the $X$-colored vertices of $G$. It is shown that for every integer $t$ with $\mathop {\mathrm rad}\nolimits _XG \le t \le \mathop {\mathrm diam}\nolimits _XG$, there exist at least one vertex $v$ with $e_X(v)=t$; while if $\mathop {\mathrm rad}\nolimits _XG \le t \le s_X$, then there are at least two such vertices. The $X$-center $C_X(G)$ is the subgraph induced by those vertices $v$ with $e_X(v)=\mathop {\mathrm rad}\nolimits _XG$ and the $X$-periphery $P_X(G)$ is the subgraph induced by those vertices $v$ with $e_X(G)=\mathop {\mathrm diam}\nolimits _XG$. It is shown that for $k$-stratified graphs $H_1, H_2, \dots , H_k$ with colors $X_1, X_2, \dots , X_k$ and a positive integer $n$, there exists a $k$-stratified graph $G$ such that $C_{X_i}(G) \cong H_i \ (1 \le i \le k)$ and $d(C_{X_i}(G), C_{X_j}(G)) \ge n \text{for} i \ne j$. Those $k$-stratified graphs that are peripheries of $k$-stratified graphs are characterized. Other distance-related topics in stratified graphs are also discussed.
For two vertices $u$ and $v$ of a graph $G$, the closed interval $I[u, v]$ consists of $u$, $v$, and all vertices lying in some $u\text{--}v$ geodesic of $G$, while for $S \subseteq V(G)$, the set $I[S]$ is the union of all sets $I[u, v]$ for $u, v \in S$. A set $S$ of vertices of $G$ for which $I[S]=V(G)$ is a geodetic set for $G$, and the minimum cardinality of a geodetic set is the geodetic number $g(G)$. A vertex $v$ in $G$ is an extreme vertex if the subgraph induced by its neighborhood is complete. The number of extreme vertices in $G$ is its extreme order $\mathop {\mathrm ex}(G)$. A graph $G$ is an extreme geodesic graph if $g(G) = \mathop {\mathrm ex}(G)$, that is, if every vertex lies on a $u\text{--}v$ geodesic for some pair $u$, $ v$ of extreme vertices. It is shown that every pair $a$, $ b$ of integers with $0 \le a \le b$ is realizable as the extreme order and geodetic number, respectively, of some graph. For positive integers $r, d,$ and $k \ge 2$, it is shown that there exists an extreme geodesic graph $G$ of radius $r$, diameter $d$, and geodetic number $k$. Also, for integers $n$, $ d, $ and $k$ with $2 \le d < n$, $2 \le k < n$, and $n -d - k +1 \ge 0$, there exists a connected extreme geodesic graph $G$ of order $n$, diameter $d$, and geodetic number $k$. We show that every graph of order $n$ with geodetic number $n-1$ is an extreme geodesic graph. On the other hand, for every pair $k$, $ n$ of integers with
$2 \le k \le n-2$, there exists a connected graph of order $n$ with geodetic number $k$ that is not an extreme geodesic graph.
For two vertices u and v in a connected graph G, the set I(u, v) consists of all those vertices lying on a u − v geodesic in G. For a set S of vertices of G, the union of all sets I(u, v) for u, v ∈ S is denoted by I(S). A set S is convex if I(S) = S. The convexity number con(G) is the maximum cardinality of a proper convex set in G. A convex set S is maximum if |S| = con(G). The cardinality of a maximum convex set in a graph G is the convexity number of G. For a nontrivial connected graph H, a connected graph G is an H-convex graph if G contains a maximum convex set S whose induced subgraph is S = H. It is shown that for every positive integer k, there exist k pairwise nonisomorphic graphs H1, H2,...,Hk of the same order and a graph G that is Hi-convex for all i (1 ≤ i ≤ k). Also, for every connected graph H of order k ≥ 3 with convexity number 2, it is shown that there exists an H-convex graph of order n for all n ≥ k + 1. More generally, it is shown that for every nontrivial connected graph H, there exists a positive integer N and an H-convex graph of order n for every integer n ≥ N.
A 2-stratified graph G is a graph whose vertex set has been partitioned into two subsets, called the strata or color classes of G. Two 2-stratified graphs G and H are isomorphic if there exists a color-preserving isomorphism ϕ from G to H. A 2-stratified graph G is said to be homogeneously embedded in a 2-stratified graph H if for every vertex x of G and every vertex y of H, where x and y are colored the same, there exists an induced 2-stratified subgraph H 0 of H containing y and a color-preserving isomorphism ϕ from G to H0 such that ϕ(x) = y. A 2-stratified graph F of minimum order in which G can be homogeneously embedded is called a frame of G and the order of F is called the framing number fr(G) of G. It is shown that every 2-stratified graph can be homogeneously embedded in some 2-stratified graph. For a graph G, a 2-stratified graph F of minimum order in which every 2-stratification of G can be homogeneously embedded is called a fence of G and the order of F is called the fencing number fe(G) of G. The fencing numbers of some well-known classes of graphs are determined. It is shown that if G is a vertex-transitive graph of order n that is not a complete graph then fe(G) = 2n.
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 ∈ V (G) assigned c(x), such that d(u, v) + |c(u) − c(v)| ≥ 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 ac(c) of a radio antipodal coloring c of G is the maximum color assigned to a vertex of G. The radio antipodal chromatic number ac(G) of G is min{ac(c)} over all radio antipodal colorings c of G. Radio antipodal chromatic numbers of paths are discussed and upper and lower bounds are presented. Furthermore, upper and lower bounds for radio antipodal chromatic numbers of graphs are given in terms of their diameter and other invariants.
Let G be a nontrivial connected graph on which is defined a coloring c : E(G) → {1, 2, . . . , k}, k ∈ N, of the edges of G, where adjacent edges may be colored the same. A path P in G is a rainbow path if no two edges of P are colored the same. The graph G is rainbow-connected if G contains a rainbow u − v path for every two vertices u and v of G. The minimum k for which there exists such a k-edge coloring is the rainbow connection number rc(G) of G. If for every pair u, v of distinct vertices, G contains a rainbow u − v geodesic, then G is strongly rainbow-connected. The minimum k for which there exists a k-edge coloring of G that results in a strongly rainbow-connected graph is called the strong rainbow connection number src(G) of G. Thus rc(G) ≤ src(G) for every nontrivial connected graph G. Both rc(G) and src(G) are determined for all complete multipartite graphs G as well as other classes of graphs. For every pair a, b of integers with a ≥ 3 and b ≥ (5a − 6)/3, it is shown that there exists a connected graph G such that rc(G) = a and src(G) = b.
For an ordered set W = {w1, w2, . . . , wk} 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(v|W) = (d(v, w1), d(v, w2), . . . , d(v, wk)), 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 dim G. A set S of vertices in G is a dominating set for G if every vertex of G that is not in S is adjacent to some vertex of S. The minimum cardinality of a dominating set is the domination number γ(G). A set of vertices of a graph G that is both resolving and dominating is a resolving dominating set. The minimum cardinality of a resolving dominating set is called the resolving domination number γr(G). In this paper, we investigate the relationship among these three parameters.
For a vertex v of a connected oriented graph D and an ordered set W = [wi, w2,.. •, wk} of vertices of D, Ihe (directed distcince) representation of v with respect to W is the ordered fc-tuple r(v \ W) = (d(v, w1),d(v, w2 ), •.. ,d(v, wk )), where d(v, wi ) is Ihe directed distance from v to wi . The set W is a resolving set for D if every two distinct vertices of D have distinct representations. The minimum cardinality of a resolving set for D is the (directed distance) dimension dhn(D) of D. The dimension of a connected oriented graph need not be defined. Those oriented graphs with dimension 1 are characterized. We discuss the problem of determining the largest dimension of an oriented graph with a fixed order. It is shown that if the outdegree of every vertex of a connected oriented graph D of order n is at least 2 and dim(D) is defined, then dim(D) ≤ n - 3 and this bound is sharp.
For two vertices $u$ and $v$ of a connected graph $G$, the set $I(u, v)$ consists of all those vertices lying on a $u$–$v$ geodesic in $G$. For a set $S$ of vertices of $G$, the union of all sets $I(u,v)$ for $u, v \in S$ is denoted by $I(S)$. A set $S$ is a convex set if $I(S) = S$. The convexity number $\mathop {\mathrm con}(G)$ of $G$ is the maximum cardinality of a proper convex set of $G$. A convex set $S$ in $G$ with $|S| = \mathop {\mathrm con}(G)$ is called a maximum convex set. A subset $T$ of a maximum convex set $S$ of a connected graph $G$ is called a forcing subset for $S$ if $S$ is the unique maximum convex set containing $T$. The forcing convexity number $f(S, \mathop {\mathrm con})$ of $S$ is the minimum cardinality among the forcing subsets for $S$, and the forcing convexity number $f(G, \mathop {\mathrm con})$ of $G$ is the minimum forcing convexity number among all maximum convex sets of $G$. The forcing convexity numbers of several classes of graphs are presented, including complete bipartite graphs, trees, and cycles. For every graph $G$, $f(G, \mathop {\mathrm con}) \le \mathop {\mathrm con}(G)$. It is shown that every pair $a$, $ b$ of integers with $0 \le a \le b$ and $b \ge 3$ is realizable as the forcing convexity number and convexity number, respectively, of some connected graph. The forcing convexity number of the Cartesian product of $H \times K_2$ for a nontrivial connected graph $H$ is studied.