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

2.
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.  相似文献   

3.
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.  相似文献   

4.
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).  相似文献   

5.
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.  相似文献   

6.
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.  相似文献   

7.
It is proved that any one-to-one edge map f from a 3-connected graph G onto a graph G′, G and G′ possibly infinite, satisfying f(C) is a circuit in G′ whenever C is a circuit in G is induced by a vertex isomorphism. This generalizes a result of Whitney which hypothesizes f(C) is a circuit in G′ if and only if C is a circuit in G.  相似文献   

8.
A compact subset X of a polyhedron P is cellular in P if there is a pseudoisotropy of P shrinking precisely X to a point. A proper surjection between polyhedra f:PQ is cellular if each point inverse of f is cellular in P. It is shown that if f:PQ is a cellular map and either P or Q is a generalized n-manifold, n≠4, then f is approximable by homeomorphisms. Also, if P or Q is an n-manifold with boundary, n≠4, 5, then a cellular map f:PQ is approximable by homeomorphisms. A cellularity criterion for a special class of cell-like sets in polyhedra is established.  相似文献   

9.
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.  相似文献   

10.
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.  相似文献   

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.
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.  相似文献   

13.
We show that a completely regular space Y is a p-space (a ?ech-complete space, a locally compact space) if and only if given a dense subspace A of any topological space X and a continuous f: AY there are a p-embedded subset (resp. a G δ-subset, an open subset) M of X containing A and a quasicontinuous subcontinuous extension f*: M → Y of f continuous at every point of A. A result concerning a continuous extension to a residual set is also given.  相似文献   

14.
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.  相似文献   

15.
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.  相似文献   

16.
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.  相似文献   

17.
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.  相似文献   

18.
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.  相似文献   

19.
A graph is point determining if distinct vertices have distinct neighbourhoods. A realization of a point determining graph H is a point determining graph G such that each vertex-removed subgraph G-x which is point determining, is isomorphic to H. We study the fine structure of point determining graphs, and conclude that every point determining graph has at most two realizations.A full homomorphism of a graph G to a graph H is a vertex mapping f such that for distinct vertices u and v of G, we have uv an edge of G if and only if f(u)f(v) is an edge of H. For a fixed graph H, a full H-colouring of G is a full homomorphism of G to H. A minimal H-obstruction is a graph G which does not admit a full H-colouring, such that each proper induced subgraph of G admits a full H-colouring. We analyse minimal H-obstructions using our results on point determining graphs. We connect the two problems by proving that if H has k vertices, then a graph with k+1 vertices is a minimal H-obstruction if and only if it is a realization of H. We conclude that every minimal H-obstruction has at most k+1 vertices, and there are at most two minimal H-obstructions with k+1 vertices.We also consider full homomorphisms to graphs H in which loops are allowed. If H has ? loops and k vertices without loops, then every minimal H-obstruction has at most (k+1)(?+1) vertices, and, when both k and ? are positive, there is at most one minimal H-obstruction with (k+1)(?+1) vertices.In particular, this yields a finite forbidden subgraph characterization of full H-colourability, for any graph H with loops allowed.  相似文献   

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号