A linear algorithm for the domination number of a series-parallel graph

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.     

Circuit preserving edge maps

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.     

Cellularity in polyhedra

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:P→Q is cellular if each point inverse of f is cellular in P. It is shown that if f:P→Q 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:P→Q is approximable by homeomorphisms. A cellularity criterion for a special class of cell-like sets in polyhedra is established.     

Frobenius splitting and geometry of G-Schubert varieties

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 G₂. Finally we also extend the Frobenius splitting results to the more general class of R-Schubert varieties.     

Finding large cycles in Hamiltonian graphs

We show how to find in Hamiltonian graphs a cycle of length n^{Ω(1/loglogn)}=exp(Ω(logn/loglogn)). This is a consequence of a more general result in which we show that if G has a maximum degree d and has a cycle with k vertices (or a 3-cyclable minor H with k vertices), then we can find in O(n³) time a cycle in G of length k^Ω(1/logd). From this we infer that if G has a cycle of length k, then one can find in O(n³) time a cycle of length k^{Ω(1/(log(n/k)+loglogn))}, which implies the result for Hamiltonian graphs. Our results improve, for some values of k and d, a recent result of Gabow (2004) [11] showing that if G has a cycle of length k, then one can find in polynomial time a cycle in G of length . We finally show that if G has fixed Euler genus g and has a cycle with k vertices (or a 3-cyclable minor H with k vertices), then we can find in polynomial time a cycle in G of length f(g)k^Ω(1), running in time O(n²) for planar graphs.     

Selection over classes of ordinals expanded by monadic predicates

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 M∈C, we say that φ is a selector for φ over C.For a monadic formula φ(X,Y) and ordinals α≤ω₁ 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.     

Building blocks for the variety of absolute retracts

Given a graph H with a labelled subgraph G, a retraction of H to G is a homomorphism r:H→G 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 AR_k 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 AR_k⊂NUF_k+1, where NUF_k+1 is the variety of graphs that admit a near unanimity function of arity k+1.     

The interval function of a connected graph and road systems

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.     

Graphs with small boundary

For a pair of vertices x and y in a graph G, we denote by d_G(x,y) the distance between x and y in G. We call x a boundary vertex of y if x and y belong to the same component and d_G(y,v)?d_G(y,x) for each neighbor v of x in G. A boundary vertex of some vertex is simply called a boundary vertex, and the set of boundary vertices in G is called the boundary of G, and is denoted by B(G).In this paper, we investigate graphs with a small boundary. Since a pair of farthest vertices are boundary vertices, |B(G)|?2 for every connected graph G of order at least two. We characterize the graphs with boundary of order at most three. We cannot give a characterization of graphs with exactly four boundary vertices, but we prove that such graphs have minimum degree at most six. Finally, we give an upper bound to the minimum degree of a connected graph G in terms of |B(G)|.     

Steiner intervals and Steiner geodetic numbers in distance-hereditary graphs

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.     

Deformation of CR-manifolds,minimal points and CR-manifolds with the microlocal analytic extension property

LetM be a smooth CR-manifold embedded into ? ⁿ . Letp be a point inM and letC be a small truncated cone inM (in suitable Euclidean coordinates onM) with vertexp which “symmetry axis” is a real vector in the complex tangent space. Then one can deformM into a smooth CR-manifoldM _d letting fixed all points outsideC in such a way thatp is a minimal point ofM _d . This result is used to give a new proof of the fact that wedge extendability of continuous CR-functions propagates along the CR-orbits of a CR-manifold. It allows also to prove the following natural result which was conjectured by Trepreau. LetM be a smooth generic CR-manifold in ? ⁿ . SupposeM consists of one single CR-orbit. Then each continuous CR-function onM is wedge extendable at any point ofM. Uniqueness theorems for continuous CR-functions are derived.     

Every vertex a king

A king in a tournament is a vertex which can reach every other vertex via a 1-path or 2-path. A new inductive proof is given for the existence of an n-tournament with exactly k kings for all integers n ? k ? 1 with the following exceptions: k = 2 with n arbitrary, and n = k = 4 (in which cases no such n-tournament exists). Also, given an n-tournament T, the smallest order m is determined so that there exists an m-tournament W which contains T as a subtournament and so that every vertex of W is a king. Bounds are obtained in a similar problem in which the kings of W are exactly the vertices of T.     

Powerful alliances in graphs

For a graph G=(V,E), a non-empty set S⊆V is a defensive alliance if for every vertex v in S, v has at most one more neighbor in V−S than it has in S, and S is an offensive alliance if for every v∈V−S that has a neighbor in S, v has more neighbors in S than in V−S. A powerful alliance is both defensive and offensive. We initiate the study of powerful alliances in graphs.     

The entire graph of a bridgeless connected plane graph is hamiltonian

In this paper we show that the entire graph of a bridgeless connected plane graph is hamiltonian, and that the entire graph of a plane block is hamiltonian connected and vertex pancyclic. In addition, we show that in any block G which is not a circuit, given a vertex v of G and a circuit k of G, there is a path p, suspended in G, such that p is a path in k of length at least 1 and G ? E(p) ? V₀(G ? E(p)) is a block which includes v.     

Some well-posed functional equations which generate semigroups

Consider the abstract linear functional equation (FE) (Dx)(t) = f(t) (t ? 0), x(t) = ?(t) (t ? 0) in a Banach space B. A theorem is proven which contains the following result as a special case. Let Y(R; B; η) be a L^p-space or C₀-space on R = (?t8, ∞), with a suitable weight function η, and with values in B. Let D be a closed (unbounded) causal linear operator in Y(R; B; η), which commutes with translations. Suppose that D + λI has a continuous causal inverse for some complex λ, and that D restricted to those functions in Y(R;B;η) which vanish on R^? = (?∞, 0] has a continuous causal inverse. Then (FE) generates a strongly continuous semigroup of translation type on a Banach space, which is essentially the cross product of the restriction of the domain of D to R^? and Y(R⁺; B; η). Examples with B = Cⁿ on how the theory applies to a neutral functional differential equation, a difference equation, a Volterra integrodifferential equation (with nonintegrable kernel but integrable resolvent), and a fractional order functional differential equation are given. Also, an abstract neutral functional differential equation in a Hilbert space is studied and applications to an abstract Volterra integrodifferential equation in a Banach space are indicated.     

Finite groups with some maximal subgroups of Sylow subgroups ℳ-supplemented

A subgroup H of a group G is said to be ?-supplemented in G if there exists a subgroup B of G such that G = HB and TB < G for every maximal subgroup T of H. In this paper, we obtain the following statement: Let ? be a saturated formation containing all supersolvable groups and H be a normal subgroup of G such that G/H ε ?. Suppose that every maximal subgroup of a noncyclic Sylow subgroup of F*(H), having no supersolvable supplement in G, is ?-supplemented in G. Then G ε ?.     

Subspaces of matrices with special rank properties

Let K be a field and let M_m×n(K) denote the space of m×n matrices over K. We investigate properties of a subspace M of M_m×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 M_m×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.     

Construction for bicritical graphs and k-extendable bipartite graphs

A graph G is said to be bicritical if G-u-v has a perfect matching for every choice of a pair of points u and v. Bicritical graphs play a central role in decomposition theory of elementary graphs with respect to perfect matchings. As Plummer pointed out many times, the structure of bicritical graphs is far from completely understood. This paper presents a concise structure characterization on bicritical graphs in terms of factor-critical graphs and transversals of hypergraphs. A connected graph G with at least 2k+2 points is said to be k-extendable if it contains a matching of k lines and every such matching is contained in a perfect matching. A structure characterization for k-extendable bipartite graphs is given in a recursive way. Furthermore, this paper presents an O(mn) algorithm for determining the extendability of a bipartite graph G, the maximum integer k such that G is k-extendable, where n is the number of points and m is the number of lines in G.     

An approximation theorem in shape theory

In this paper it is shown that if X is a compactum in the interior of a PL manifold M and if U is a neighborhood of X in M, then there is a compactum X′ in U such that X and X′ have the same relative shape in U and the embedding dimension of X′ equals the fundamental dimension of X. Whenever the dimension of M is not equal to three, the relative shape equivalence from X′ to X can be realized by an infinite isotopy of M.     

On a generalization of distance sets

A subset X in the d-dimensional Euclidean space is called a k-distance set if there are exactly k distinct distances between two distinct points in X and a subset X is called a locally k-distance set if for any point x in X, there are at most k distinct distances between x and other points in X.Delsarte, Goethals, and Seidel gave the Fisher type upper bound for the cardinalities of k-distance sets on a sphere in 1977. In the same way, we are able to give the same bound for locally k-distance sets on a sphere. In the first part of this paper, we prove that if X is a locally k-distance set attaining the Fisher type upper bound, then determining a weight function w, (X,w) is a tight weighted spherical 2k-design. This result implies that locally k-distance sets attaining the Fisher type upper bound are k-distance sets. In the second part, we give a new absolute bound for the cardinalities of k-distance sets on a sphere. This upper bound is useful for k-distance sets for which the linear programming bound is not applicable. In the third part, we discuss about locally two-distance sets in Euclidean spaces. We give an upper bound for the cardinalities of locally two-distance sets in Euclidean spaces. Moreover, we prove that the existence of a spherical two-distance set in (d−1)-space which attains the Fisher type upper bound is equivalent to the existence of a locally two-distance set but not a two-distance set in d-space with more than d(d+1)/2 points. We also classify optimal (largest possible) locally two-distance sets for dimensions less than eight. In addition, we determine the maximum cardinalities of locally two-distance sets on a sphere for dimensions less than forty.