Let V be a finite set and $\mathcal{M}$ a collection of subsets of V. Then $\mathcal{M}$ is an alignment of V if and only if $\mathcal{M}$ is closed under taking intersections and contains both V and the empty set. If $\mathcal{M}$ is an alignment of V, then the elements of $\mathcal{M}$ are called convex sets and the pair $(V,\mathcal{M})$ is called an aligned space. If $S\subseteq V$, then the convex hull of S is the smallest convex set that contains S. Suppose $X\in\mathcal{M}$. Then $x\in X$ is an extreme point for X if $X\setminus\{x\}\in\mathcal{M}$. The collection of all extreme points of X is denoted by $\text{{\it ex\/}}(X)$. A convex geometry on a finite set is an aligned space with the additional property that every convex set is the convex hull of its extreme points. Let G be a connected graph. A set S of vertices is g-convex if for every pair $u,v$ of vertices in S, every vertex that belongs to some u-v geodesic (shortest path) is also in S. A set S of vertices in G is k-Steiner-convex, denoted by $g_k$-convex, if, for every set T of k vertices of S, every vertex that belongs to some Steiner tree for T, i.e., a subtree of G of smallest size containing T, is also in S. Let $R=\{k_1,k_2,\dots,k_t\}$ be a collection of positive integers such that $2\leq k_1

Let G be connected graph and S a set of vertices of G. Then a Steiner tree for S is a connected subgraph of G of smallest size (number of edges) that contains S. The size of such a subgraph is called the Steiner distance for S and is denoted by d(S). For a vertex v of G, and integer n, 2 ≤n ≤ |V(G)|, the Steiner n-eccentricity en(v) of v is defined as en(v) = max{d(S)|S ⊆V(G), |S| = n, and v ∈ S}. The Steiner n-radius radnG and Steiner n-diameter diamnG are defined as the minimum and maximum n-eccentricity respectively, taken over all vertices of G. Relationships between radnG and diamnG are given if G is a tree, and a conjecture (with some supporting results) is made that relates these parameters for general graphs. The subgraph induced by these vertices with n-eccentricity radnG is called the Steiner n-center of G and is denoted by Cn(G). It is shown that every graph is the Steiner n-center of some graph. The Steiner n-distance of a vertex v, denoted by dn(v), is defined by dn(v) = ∑{d(S)|v ∈S, |S| =n}. The Steiner n-median Mn(G) of G is the subgraph induced by those vertices with minimum Steiner n-distance. Algorithms for finding Cn(T) and Mn(T) for a tree T are described. It is shown that the distance between the Cn(T) and Mn(T) for a tree T can be arbitrarily large. Eccentricity measures are defined that extend those of the Steiner n-eccentricity and Steiner n-distance of a vertex. Then it is shown that every vertex on a shortest path between the Steiner n-center and Steiner n-median of a tree belongs to a “center” relative to one of these eccentricity measures. © 1999 John Wiley & Sons, Inc. Networks 34: 258–263, 1999

Let G be a connected graph and S ⊆ V(G). Then, the Steiner distance of S in G, denoted by dG(S), is the smallest number of edges in a connected subgraph of G that contains S. A connected graph G is k-Steiner distance hereditary, k ≥ 2, if for every S ⊆ V(G) such that |S| = k and every connected induced subgraph H of G containing S, dH(S) = dG(S). Some general properties about the cycle structure of k-Steiner distance hereditary graphs are established. These are then used to characterize 3-Steiner distance hereditary graphs. © 1997 John Wiley & Sons, Inc. Networks 30: 243–253, 1997

Let G be a connected graph and $S \subseteq V( G )$. Then the Steiner distance of S in G, denoted by $d_G ( S )$, is the smallest number of edges in a connected subgraph of G that contains S. A connected graph G is k-Steiner distance-hereditary, $k \geq 2$, if, for every $S \subseteq V( G )$ such that $|S| = k$ and every connected induced subgraph H of G containing $S,d_H ( S ) = d_G ( S )$. It is shown that if G is 2-Steiner distance-hereditary, then G is k-Steiner distance-hereditary for all $k \geq 2$. Furthermore, it is shown that if G is k-Steiner distance-hereditary $( k \geq 3 )$, then G need not be $( k - 1 )$-Steiner distance-hereditary. An efficient algorithm for determining the Steiner distance of a set of k vertices in a k-Steiner distance-hereditary graph is discussed, and a characterization of 2-Steiner distance-hereditary graphs that leads to an efficient algorithm for testing whether a graph is 2-Steiner distance-hereditary is given.

Abstract A graphical property P is said to be hereditary (strongly hereditary) if every induced subgraph (subgraph) of a graph with property P also has property P. If P is a graphical property, then the P‐connectivity of a graph is the minimum number of vertices whose removal from G produces the trivial graph or a disconnected graph each of whose components has property P. Several analogs and generalizations of results concerning the ordinary connectivity of a graph are established for the P‐connectivity of a graph, with respect to hereditary properties P. If P is a graphical property, then the P‐edge‐connectivity of a graph is defined similarly to the P‐connectivity. Several results concerning the P‐edge‐connectivity of a graph with respect to strongly hereditary properties P are established. Moreover, a generalization of Whitney's inequalities is given.

The concepts of nth degrees and nth-order odd vertices in graphs are introduced. The first degree of a vertex v in a graph G is the degree of v, while the nth degree ($n\geqq 2$) of $v $ is the sum of the $(n - 1)$st degrees of the vertices adjacent to $v $ in G. By a first-order odd vertex in a graph G is meant an (ordinary) odd vertex in G, while for $n\geqq 2$, an nth-order odd vertex of G is a vertex adjacent to an odd number of $(n - 1)$st-order odd vertices. The number of nth-order odd vertices, $n = 1,2, \cdots $, is investigated. A sequence $s_{1}, s_{2}, \cdots ,s_n , \cdots $ of integers is defined to be a generalized odd vertex sequence if there exists a graph G containing exactly $s_{n}$nth-order odd vertices for every positive integer n. Generalized odd vertex sequences are characterized. Relationships between the nth degrees of the vertices of a graph G and the walks of length n in G are described. The analogous problem for digraphs is also discussed.