Let G be a connected graph and S a set of vertices of G. The Steiner distance of S is the smallest number of edges in a connected subgraph of G that contains S and is denoted by dG(S) or d(S). The Steiner n-eccentricity en(v) and Steiner n-distance dn(v) of a vertex v in G are defined as en(v)=max{d(S)| SV(G), |S|=n and vS} and dn(v)=∑{d(S)| SV(G), |S|=n and vS}, respectively. The Steiner n-center Cn(G) of G is the subgraph induced by the vertices of minimum n-eccentricity. The Steiner n-median Mn(G) of G is the subgraph induced by those vertices with minimum Steiner n-distance. Let T be a tree. Oellermann and Tian [O.R. Oellermann, S. Tian, Steiner centers in graphs, J. Graph Theory 14 (1990) 585–597] showed that Cn(T) is contained in Cn+1(T) for all n2. Beineke et al. [L.W. Beineke, O.R. Oellermann, R.E. Pippert, On the Steiner median of a tree, Discrete Appl. Math. 68 (1996) 249–258] showed that Mn(T) is contained in Mn+1(T) for all n2. Then, Oellermann [O.R. Oellermann, On Steiner centers and Steiner medians of graphs, Networks 34 (1999) 258–263] asked whether these containment relationships hold for general graphs. In this note we show that for every n2 there is an infinite family of block graphs G for which Cn(G)Cn+1(G). We also show that for each n2 there is a distance–hereditary graph G such that Mn(G)Mn+1(G). Despite these negative examples, we prove that if G is a block graph then Mn(G) is contained in Mn+1(G) for all n2. Further, a linear time algorithm for finding the Steiner n-median of a block graph is presented and an efficient algorithm for finding the Steiner n-distances of all vertices in a block graph is described. 相似文献
The Steiner distance of a set S of vertices in a connected graph G is the minimum size among all connected subgraphs of G containing S. For n ≥ 2, the n-eccentricity en(ν) of a vertex ν of a graph G is the maximum Steiner distance among all sets S of n vertices of G that contains ν. The n-diameter of G is the maximum n-eccentricity among the vertices of G while the n-radius of G is the minimum n-eccentricity. The n-center of G is the subgraph induced by those vertices of G having minimum n-eccentricity. It is shown that every graph is the n-center of some graph. Several results on the n-center of a tree are established. In particular, it is shown that the n-center of a tree is a tree and those trees that are n-centers of trees are characterized. 相似文献
Let G be a connected graph and S⊆V(G). Then the Steiner distance of S, denoted by dG(S), is the smallest number of edges in a connected subgraph of G containing S. Such a subgraph is necessarily a tree called a Steiner tree for S. The Steiner interval for a set S of vertices in a graph, denoted by I(S) is the union of all vertices that belong to some Steiner tree for S. If S={u,v}, then I(S) is the interval I[u,v] between u and v. A connected graph G is 3-Steiner distance hereditary (3-SDH) if, for every connected induced subgraph H of order at least 3 and every set S of three vertices of H, dH(S)=dG(S). The eccentricity of a vertex v in a connected graph G is defined as e(v)=max{d(v,x)|x∈V(G)}. A vertex v in a graph G is a contour vertex if for every vertex u adjacent with v, e(u)?e(v). The closure of a set S of vertices, denoted by I[S], is defined to be the union of intervals between pairs of vertices of S taken over all pairs of vertices in S. A set of vertices of a graph G is a geodetic set if its closure is the vertex set of G. The smallest cardinality of a geodetic set of G is called the geodetic number of G and is denoted by g(G). A set S of vertices of a connected graph G is a Steiner geodetic set for G if I(S)=V(G). The smallest cardinality of a Steiner geodetic set of G is called the Steiner geodetic number of G and is denoted by sg(G). We show that the contour vertices of 3-SDH and HHD-free graphs are geodetic sets. For 3-SDH graphs we also show that g(G)?sg(G). An efficient algorithm for finding Steiner intervals in 3-SDH graphs is developed. 相似文献
Suppose G = (V, E) is a graph in which every vertex x has a non-negative real number w(x) as its weight. The w-distance sum of a vertex y is DG, w(y) = σx?vd(y, x)w(x). The w-median of G is the set of all vertices y with minimum w-distance sum DG,w(y). This paper shows that the w-median of a connected strongly chordal graph G is a clique when w(x) is positive for all vertices x in G. 相似文献
A routing R of a graph G is a set of n(n ? 1) elementary paths R(u, v) specified for all ordered pairs (u, v) of vertices of G. The vertex-forwarding index ξ(G) of G, is defined by Where ξ(G, R) is the maximum number of paths of the routing R passing through any vertex of G and the minimum is taken over all the routings of G. Let Gp denote the random graph on n vertices with edge probability p and let m = np. It is proved among other things that, under natural growth conditions on the function p = p(n), the ratio Tends to 1 in probability as n tends to infinity. 相似文献
Given a graph G and a subset S of the vertex set of G, the discrepancy of S is defined as the difference between the actual and expected numbers of the edges in the subgraph induced on S. We show that for every graph with n vertices and e edges, n < e < n(n ? 1)/4, there is an n/2-element subset with the discrepancy of the order of magnitude of \documentclass{article}\pagestyle{empty}\begin{document}$\sqrt {ne}$\end{document} For graphs with fewer than n edges, we calculate the asymptotics for the maximum guaranteed discrepancy of an n/2-element subset. We also introduce a new notion called “bipartite discrepancy” and discuss related results and open problems. 相似文献
Let G be a connected graph and S a nonempty set of vertices of G. A Steiner tree for S is a connected subgraph of G containing S that has a minimum number of edges. The Steiner interval for S is the collection of all vertices in G that belong to some Steiner tree for S. Let k≥2 be an integer. A set X of vertices of G is k-Steiner convex if it contains the Steiner interval of every set of k vertices in X. A vertex x∈X is an extreme vertex of X if X?{x} is also k-Steiner convex. We call such vertices k-Steiner simplicial vertices. We characterize vertices that are 3-Steiner simplicial and give characterizations of two classes of graphs, namely the class of graphs for which every ordering produced by Lexicographic Breadth First Search is a 3-Steiner simplicial ordering and the class for which every ordering of every induced subgraph produced by Maximum Cardinality Search is a 3-Steiner simplicial ordering. 相似文献
A Steiner tree for a set S of vertices in a connected graph G is a connected subgraph of G with a smallest number of edges that contains S. The Steiner interval I(S) of S is the union of all the vertices of G that belong to some Steiner tree for S. If S={u,v}, then I(S)=I[u,v] is called the interval between u and v and consists of all vertices that lie on some shortest u-v path in G. The smallest cardinality of a set S of vertices such that ?u,v∈SI[u,v]=V(G) is called the geodetic number and is denoted by g(G). The smallest cardinality of a set S of vertices of G such that I(S)=V(G) is called the Steiner geodetic number of G and is denoted by sg(G). We show that for distance-hereditary graphs g(G)?sg(G) but that g(G)/sg(G) can be arbitrarily large if G is not distance hereditary. An efficient algorithm for finding the Steiner interval for a set of vertices in a distance-hereditary graph is described and it is shown how contour vertices can be used in developing an efficient algorithm for finding the Steiner geodetic number of a distance-hereditary graph. 相似文献
Let G = G(n) be a graph on n vertices with maximum degree Δ =Δ (n). Assign to each vertex v of G a list L(v) of colors by choosing each list independently and uniformly at random from all k‐subsets of a color set of size . Such a list assignment is called a random‐list assignment. In this paper, we are interested in determining the asymptotic probability (as n →∞) of the existence of a proper coloring φ of G, such that for every vertex v of G, a so‐called L‐coloring. We give various lower bounds on σ, in terms of n, k, and Δ, which ensures that with probability tending to 1 as n →∞ there is an L‐coloring of G. In particular, we show, for all fixed k and growing n, that if and , then the probability that G has an L‐coloring tends to 1 as . If and , then the same conclusion holds provided that . We also give related results for other bounds on Δ, when k is constant or a strictly increasing function of n. 相似文献
A partial Steiner (n, k, l)-system or briefly (n, k, l)-system is a pair (V, S), where V is an n-set and S is a collection of k-subsets of V, such that every l-subset of V is contained in at most one k-subset of S. A subset X ? V is called independent if [X]k ∩ S = 0. The size of the largest independent set in S is denoted by α(S). Define The purpose of this note is to prove that for every k, l, k > l holds, where c, d are positive constants depending on k and l only. 相似文献