首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 15 毫秒
1.
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,vSI[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.  相似文献   

2.
Linda Eroh 《Discrete Mathematics》2008,308(18):4212-4220
Let G be a connected graph and SV(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)|xV(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.  相似文献   

3.
We apply equivariant joins to give a new and more transparent proof of the following result: if G is a compact Hausdorff group and X a G-ANR (respectively, a G-AR), then for every closed normal subgroup H of G, the H-orbit space X/H is a G/H-ANR (respectively, a G/H-AR). In particular, X/G is an ANR (respectively, an AR).  相似文献   

4.
Let (g,δ?) be a Lie bialgebra. Let (U?(g),Δ?) a quantization of (g,δ?) through Etingof-Kazhdan functor. We prove the existence of a L-morphism between the Lie algebra C(g)=Λ(g) and the tensor algebra (without unit) T+U=T+(U?(g)[−1]) with Lie algebra structure given by the Gerstenhaber bracket. When s is a twist for (g,δ), we deduce from the formality morphism the existence of a quantum twist F. When (g,δ,r) is a coboundary Lie bialgebra, we get the existence of a quantization R of r.  相似文献   

5.
T?naz Ekim 《Discrete Mathematics》2009,309(19):5849-5856
Given integers j and k and a graph G, we consider partitions of the vertex set of G into j+k parts where j of these parts induce empty graphs and the remaining k induce cliques. If such a partition exists, we say G is a (j,k)-graph. For a fixed j and k we consider the maximum order n where every graph of order n is a (j,k)-graph. The split-chromatic number of G is the minimum j where G is a (j,j)-graph. Further, the cochromatic number is the minimum j+k where G is a (j,k)-graph. We examine some relations between cochromatic, split-chromatic and chromatic numbers. We also consider some computational questions related to chordal graphs and cographs.  相似文献   

6.
Let X be an equivariant embedding of a connected reductive group G over an algebraically closed field k of positive characteristic. Let B denote a Borel subgroup of G. A G-Schubert variety in X is a subvariety of the form diag(G)⋅V, where V is a B×B-orbit closure in X. In the case where X is the wonderful compactification of a group of adjoint type, the G-Schubert varieties are the closures of Lusztig's G-stable pieces. We prove that X admits a Frobenius splitting which is compatible with all G-Schubert varieties. Moreover, when X is smooth, projective and toroidal, then any G-Schubert variety in X admits a stable Frobenius splitting along an ample divisors. Although this indicates that G-Schubert varieties have nice singularities we present an example of a nonnormal G-Schubert variety in the wonderful compactification of a group of type G2. Finally we also extend the Frobenius splitting results to the more general class of R-Schubert varieties.  相似文献   

7.
Let G be a graph. If u,vV(G), a u-vshortest path of G is a path linking u and v with minimum number of edges. The closed interval I[u,v] consists of all vertices lying in some u-v shortest path of G. For SV(G), the set I[S] is the union of all sets I[u,v] for u,vS. We say that S is a convex set if I[S]=S. The convex hull of S, denoted Ih[S], is the smallest convex set containing S. A set S is a hull set of G if Ih[S]=V(G). The cardinality of a minimum hull set of G is the hull number of G, denoted by hn(G). In this work we prove that deciding whether hn(G)≤k is NP-complete.We also present polynomial-time algorithms for computing hn(G) when G is a unit interval graph, a cograph or a split graph.  相似文献   

8.
Given a graph H with a labelled subgraph G, a retraction of H to G is a homomorphism r:HG such that r(x)=x for all vertices x in G. We call G a retract of H. While deciding the existence of a retraction to a fixed graph G is NP-complete in general, necessary and sufficient conditions have been provided for certain classes of graphs in terms of holes, see for example Hell and Rival.For any integer k?2 we describe a collection of graphs that generate the variety ARk of graphs G with the property that G is a retract of H whenever G is a subgraph of H and no hole in G of size at most k is filled by a vertex of H. We also prove that ARkNUFk+1, where NUFk+1 is the variety of graphs that admit a near unanimity function of arity k+1.  相似文献   

9.
A Polish group G is called a group of quasi-invariance or a QI-group, if there exist a locally compact group X and a probability measure μ on X such that (1) there exists a continuous monomorphism ? from G into X with dense image, and (2) for each gX either g?(G) and the shift μg is equivalent to μ or g?(G) and μg is orthogonal to μ. It is proved that ?(G) is a σ-compact subset of X. We show that there exists a Polish non-locally quasi-convex (and hence nonreflexive) QI-group such that its bidual is not a QI-group. It is proved also that the bidual group of a QI-group may be not a saturated subgroup of X. It is constructed a reflexive non-discrete group topology on the integers.  相似文献   

10.
A monadic formula ψ(Y) is a selector for a monadic formula φ(Y) in a structure M if ψ defines in M a unique subset P of the domain and this P also satisfies φ in M. If C is a class of structures and φ is a selector for ψ in every MC, we say that φ is a selector for φ over C.For a monadic formula φ(X,Y) and ordinals αω1 and δ<ωω, we decide whether there exists a monadic formula ψ(X,Y) such that for every Pαof order-type smaller thanδ, ψ(P,Y) selects φ(P,Y) in (α,<). If so, we construct such a ψ.We introduce a criterion for a class C of ordinals to have the property that every monadic formula φ has a selector over it. We deduce the existence of Sωω such that in the structure (ωω,<,S) every formula has a selector.Given a monadic sentence π and a monadic formula φ(Y), we decide whether φ has a selector over the class of countable ordinals satisfying π, and if so, construct one for it.  相似文献   

11.
For digraphs D and H, a mapping f:V(D)→V(H) is a homomorphism ofDtoH if uvA(D) implies f(u)f(v)∈A(H). For a fixed directed or undirected graph H and an input graph D, the problem of verifying whether there exists a homomorphism of D to H has been studied in a large number of papers. We study an optimization version of this decision problem. Our optimization problem is motivated by a real-world problem in defence logistics and was introduced recently by the authors and M. Tso.Suppose we are given a pair of digraphs D,H and a cost ci(u) for each uV(D) and iV(H). The cost of a homomorphism f of D to H is ∑uV(D)cf(u)(u). Let H be a fixed digraph. The minimum cost homomorphism problem for H, MinHOMP(H), is stated as follows: For input digraph D and costs ci(u) for each uV(D) and iV(H), verify whether there is a homomorphism of D to H and, if it does exist, find such a homomorphism of minimum cost. In our previous paper we obtained a dichotomy classification of the time complexity of when H is a semicomplete digraph. In this paper we extend the classification to semicomplete k-partite digraphs, k≥3, and obtain such a classification for bipartite tournaments.  相似文献   

12.
A core of a graph G is a path P in G that is central with respect to the property of minimizing d(P) = Συ?V(G)d(υ, P), where d(υ, P) is the distance from vertex υ to path P. We present a linear algorithm for finding a core of a tree. Since the core of a graph is not necessarily unique, we also output a list of all the vertices which are in some core.  相似文献   

13.
We introduce the notion of gi-algebra as a generalization of dual BCK-algebra, and define the notions of strong, commutative and transitive gi-algebra, and then we show that an interval ↑l = {aP | la} in a strong and commutative gi-algebra P is a lattice. Also, we define a congruence relation ~ D on a transitive gi-algebra P and show that the quotient set P/~ D is a gi-algebra and a dual BCK-algebra.  相似文献   

14.
Given a graph G=(V,E), two fixed vertices s,tV and a set F of pairs of vertices (called forbidden pairs), the problem of a path avoiding forbidden pairs is to find a path from s to t that contains at most one vertex from each pair in F. The problem is known to be NP-complete in general and a few restricted versions of the problem are known to be in P. We study the complexity of the problem for directed acyclic graphs with respect to the structure of the forbidden pairs.We write x?y if and only if there exists a path from x to y and we assume, without loss of generality, that for every forbidden pair (x,y)∈F we have x?y. The forbidden pairs have a halving structure if no two pairs (u,v),(x,y)∈F satisfy v?x or v=x and they have a hierarchical structure if no two pairs (u,v),(x,y)∈F satisfy u?x?v?y. We show that the PAFP problem is NP-hard even if the forbidden pairs have the halving structure and we provide a surprisingly simple and efficient algorithm for the PAFP problem with the hierarchical structure.  相似文献   

15.
Let K be a field and let Mm×n(K) denote the space of m×n matrices over K. We investigate properties of a subspace M of Mm×n(K) of dimension n(m-r+1) in which each non-zero element of M has rank at least r and enumerate the number of elements of a given rank in M when K is finite. We also provide an upper bound for the dimension of a constant rank r subspace of Mm×n(K) when K is finite and give non-trivial examples to show that our bound is optimal in some cases. We include a similar a bound for the maximum dimension of a constant rank subspace of skew-symmetric matrices over a finite field.  相似文献   

16.
We consider the action of a real reductive group G on a Kähler manifold Z which is the restriction of a holomorphic action of a complex reductive group H. We assume that the action of a maximal compact subgroup U of H is Hamiltonian and that G is compatible with a Cartan decomposition of H. We have an associated gradient map μp:Zp where g=kp is the Cartan decomposition of g. For a G-stable subset Y of Z we consider convexity properties of the intersection of μp(Y) with a closed Weyl chamber in a maximal abelian subspace a of p. Our main result is a Convexity Theorem for real semi-algebraic subsets Y of Z=P(V) where V is a unitary representation of U.  相似文献   

17.
A vertex u in an undirected graph G = (V, E) is said to dominate all its adjacent vertices and itself. A subset D of V is a dominating set in G if every vertex in G is dominated by a vertex in D, and is a minimum dominating set in G if no other dominating set in G has fewer vertices than D. The domination number of G is the cardinality of a minimum dominating set in G.The problem of determining, for a given positive integer k and an undirected graph G, whether G has a dominating set D in G satisfying ¦D¦ ≤ k, is a well-known NP-complete problem. Cockayne have presented a linear time algorithm for finding a minimum dominating set in a tree. In this paper, we will present a linear time algorithm for finding a minimum dominating set in a series-parallel graph.  相似文献   

18.
In this article we give a sufficient condition for a space X to have the fully closed absolute faX with the property fa(faX)=faX. An example of a compact space X such that the canonical mapping fa(α+1)Xfa(α)X (where α is a given ordinal) is not a homeomorphism is constructed. Also we give an example of a compact space X such that the canonical mapping faXX is not a homeomorphism but for which there exists a homeomorphism faXX.  相似文献   

19.
Let V be a finite nonempty set. In this paper, a road system on V (as a generalization of the set of all geodesics in a connected graph G with V(G)=V) and an intervaloid function on V (as a generalization of the interval function (in the sense of Mulder) of a connected graph G with V(G)=V) are introduced. A natural bijection of the set of all intervaloid functions on V onto the set of all road systems on V is constructed. This bijection enables to deduce an axiomatic characterization of the interval function of a connected graph G from a characterization of the set of all geodesics in G.  相似文献   

20.
An ordered n-tuple (vi1,vi2,…,vin) is called a sequential labelling of graph G if {vi1,vi2,…,vin} = V(G) and the subgraph induced by {vi1,vi2,…, vij} is connected for 1≤jn. Let σ(v;G) denote the number of sequential labellings of G with vi1=v. Vertex v is defined to be an accretion center of G if σ is maximized at v. This is shown to generalize the concept of a branch weight centroid of a tree since a vertex in a tree is an accretion center if and only if it is a centroid vertex. It is not, however, a generalization of the concept of a median since for a general graph an accretion center is not necessarily a vertex of minimum distance. A method for computing σ(v;G) based upon edge contractions is described.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号