A characterization of maximal non-k-factor-critical graphs

A graph G of order p is k-factor-critical,where p and k are positive integers with the same parity, if the deletion of any set of k vertices results in a graph with a perfect matching. G is called maximal non-k-factor-critical if G is not k-factor-critical but G+e is k-factor-critical for every missing edge e∉E(G). A connected graph G with a perfect matching on 2n vertices is k-extendable, for 1?k?n-1, if for every matching M of size k in G there is a perfect matching in G containing all edges of M. G is called maximal non-k-extendable if G is not k-extendable but G+e is k-extendable for every missing edge e∉E(G) . A connected bipartite graph G with a bipartitioning set (X,Y) such that |X|=|Y|=n is maximal non-k-extendable bipartite if G is not k-extendable but G+xy is k-extendable for any edge xy∉E(G) with x∈X and y∈Y. A complete characterization of maximal non-k-factor-critical graphs, maximal non-k-extendable graphs and maximal non-k-extendable bipartite graphs is given.     

The recognition of the class of indecomposable digraphs under low hemimorphy

Given a digraph G=(V,A), the subdigraph of G induced by a subset X of V is denoted by G[X]. With each digraph G=(V,A) is associated its dual G^?=(V,A^?) defined as follows: for any x,y∈V, (x,y)∈A^? if (y,x)∈A. Two digraphs G and H are hemimorphic if G is isomorphic to H or to H^?. Given k>0, the digraphs G=(V,A) and H=(V,B) are k-hemimorphic if for every X⊆V, with |X|≤k, G[X] and H[X] are hemimorphic. A class C of digraphs is k-recognizable if every digraph k-hemimorphic to a digraph of C belongs to C. In another vein, given a digraph G=(V,A), a subset X of V is an interval of G provided that for a,b∈X and x∈V−X, (a,x)∈A if and only if (b,x)∈A, and similarly for (x,a) and (x,b). For example, 0?, {x}, where x∈V, and V are intervals called trivial. A digraph is indecomposable if all its intervals are trivial. We characterize the indecomposable digraphs which are 3-hemimorphic to a non-indecomposable digraph. It follows that the class of indecomposable digraphs is 4-recognizable.     

On 3-Steiner simplicial orderings

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.     

Graphs admitting transitive commutative group actions

Let X be a compact metric space, and Homeo(X) be the group consisting of all homeomorphisms from X to X. A subgroup H of Homeo(X) is said to be transitive if there exists a point x∈X such that {k(x):k∈H} is dense in X. In this paper we show that, if X=G is a connected graph, then the following five conditions are equivalent: (1) Homeo(G) has a transitive commutative subgroup; (2) G admits a transitive Z²-action; (3) G admits an edge-transitive commutative group action; (4) G admits an edge-transitive Z²-action; (5) G is a circle, or a k-fold loop with k?2, or a k-fold polygon with k?2, or a k-fold complete bigraph with k?1. As a corollary of this result, we show that a finite connected simple graph whose automorphism group contains an edge-transitive commutative subgroup is either a cycle or a complete bigraph.     

Finite-to-one maps into Euclidean manifolds and spaces with disjoint disks properties

It is shown that every Euclidean manifold M has the following property for any m?1: If f:X→Y is a perfect surjection between finite-dimensional metric spaces, then the mapping space C(X,M) with the source limitation topology contains a dense Gδ-subset of maps g such that dimBm(g)?mdimf+dimY−(m−1)dimM. Here, Bm(g)={(y,z)∈Y×M||f−1(y)∩g−1(z)|?m}. The existence of residual sets of finite-to-one maps into product of manifolds and spaces having disjoint disks properties is also obtained.     

On the extendability of Bi-Cayley graphs of finite abelian groups

Let G be a finite group and A a nonempty subset (possibly containing the identity element) of G. The Bi-Cayley graph X=BC(G,A) of G with respect to A is defined as the bipartite graph with vertex set G×{0,1} and edge set {{(g,0),(sg,1)}∣g∈G,s∈A}. A graph Γ admitting a perfect matching is called n-extendable if ∣V(Γ)∣≥2n+2 and every matching of size n in Γ can be extended to a perfect matching of Γ. In this paper, the extendability of Bi-Cayley graphs of finite abelian groups is explored. In particular, 2-extendable and 3-extendable Bi-Cayley graphs of finite abelian groups are characterized.     

Pair lengths of product graphs

The pair length of a graph G is the maximum positive integer k, such that the vertex set of G can be partitioned into disjoint pairs {x,x^′}, such that d(x,x^′)?k for every x∈V(G) and x^′y^′ is an edge of G whenever xy is an edge. Chen asked whether the pair length of the cartesian product of two graphs is equal to the sum of their pair lengths. Our aim in this short note is to prove this result.     

Oberwolfach rectangular table negotiation problem

We completely solve certain case of a “two delegation negotiation” version of the Oberwolfach problem, which can be stated as follows. Let H(k,3) be a bipartite graph with bipartition X={x₁,x₂,…,x_k},Y={y₁,y₂,…,y_k} and edges x₁y₁,x₁y₂,x_ky_k−1,x_ky_k, and x_iy_i−1,x_iy_i,x_iy_i+1 for i=2,3,…,k−1. We completely characterize all complete bipartite graphs K_n,n that can be factorized into factors isomorphic to G=mH(k,3), where k is odd and mH(k,3) is the graph consisting of m disjoint copies of H(k,3).     

On (s,t)-supereulerian graphs in locally highly connected graphs

Given two nonnegative integers s and t, a graph G is (s,t)-supereulerian if for any disjoint sets X,Y⊂E(G) with |X|≤s and |Y|≤t, there is a spanning eulerian subgraph H of G that contains X and avoids Y. We prove that if G is connected and locally k-edge-connected, then G is (s,t)-supereulerian, for any pair of nonnegative integers s and t with s+t≤k−1. We further show that if s+t≤k and G is a connected, locally k-edge-connected graph, then for any disjoint sets X,Y⊂E(G) with |X|≤s and |Y≤t, there is a spanning eulerian subgraph H that contains X and avoids Y, if and only if G−Y is not contractible to K₂ or to K_2,l with l odd.     

Listing minimal edge-covers of intersecting families with applications to connectivity problems

Let G=(V,E) be a directed/undirected graph, let s,t∈V, and let F be an intersecting family on V (that is, X∩Y,X∪Y∈F for any intersecting X,Y∈F) so that s∈X and t∉X for every X∈F. An edge set I⊆E is an edge-cover of F if for every X∈F there is an edge in I from X to V−X. We show that minimal edge-covers of F can be listed with polynomial delay, provided that, for any I⊆E the minimal member of the residual family F_I of the sets in F not covered by I can be computed in polynomial time. As an application, we show that minimal undirected Steiner networks, and minimal k-connected and k-outconnected spanning subgraphs of a given directed/undirected graph, can be listed in incremental polynomial time.     

Generic uniqueness of equilibrium points

Let X be a nonempty, convex and compact subset of normed linear space E (respectively, let X be a nonempty, bounded, closed and convex subset of Banach space E and A be a nonempty, convex and compact subset of X) and f:X×X→R be a given function, the uniqueness of equilibrium point for equilibrium problem which is to find x^∗∈X (respectively, x^∗∈A) such that f(x^∗,y)≥0 for all y∈X (respectively, f(x^∗,y)≥0 for all y∈A) is studied with varying f (respectively, with both varying f and varying A). The results show that most of equilibrium problems (in the sense of Baire category) have unique equilibrium point.     

The best generalized inverse of the linear operator in normed linear space

Let X,Y be normed linear spaces, T∈L(X,Y) be a bounded linear operator from X to Y. One wants to solve the linear problem Ax=y for x (given y∈Y), as well as one can. When A is invertible, the unique solution is x=A^-1y. If this is not the case, one seeks an approximate solution of the form x=By, where B is an operator from Y to X. Such B is called a generalised inverse of A. Unfortunately, in general normed linear spaces, such an approximate solution depends nonlinearly on y. We introduce the concept of bounded quasi-linear generalised inverse T^h of T, which contains the single-valued metric generalised inverse T^M and the continuous linear projector generalised inverse T⁺. If X and Y are reflexive, we prove that the set of all bounded quasi-linear generalised inverses of T, denoted by G_H(T), is not empty In the normed linear space of all bounded homogeneous operators, the best bounded quasi-linear generalised inverse T^h of T is just the Moore-Penrose metric generalised inverse T^M. In the case, X and Y are finite dimension spaces Rⁿ and R^m, respectively, the results deduce the main result by G.R. Goldstein and J.A. Goldstein in 2000.     

Degree conditions for the partition of a graph into cycles, edges and isolated vertices

Let k,n be integers with 2≤k≤n, and let G be a graph of order n. We prove that if max{d_G(x),d_G(y)}≥(n−k+1)/2 for any x,y∈V(G) with x≠y and xy∉E(G), then G has k vertex-disjoint subgraphs H₁,…,H_k such that V(H₁)∪?∪V(H_k)=V(G) and H_i is a cycle or K₁ or K₂ for each 1≤i≤k, unless k=2 and G=C₅, or k=3 and G=K₁∪C₅.     

Galois closure of essentially finite morphisms

Let X be a reduced connected k-scheme pointed at a rational point x∈X(k). By using tannakian techniques we construct the Galois closure of an essentially finite k-morphism f:Y→X satisfying the condition H⁰(Y,O_Y)=k; this Galois closure is a torsor dominating f by an X-morphism and universal for this property. Moreover, we show that is a torsor under some finite group scheme we describe. Furthermore we prove that the direct image of an essentially finite vector bundle over Y is still an essentially finite vector bundle over X. We develop for torsors and essentially finite morphisms a Galois correspondence similar to the usual one. As an application we show that for any pointed torsor f:Y→X under a finite group scheme satisfying the condition H⁰(Y,O_Y)=k, Y has a fundamental group scheme π₁(Y,y) fitting in a short exact sequence with π₁(X,x).     

Smallest close to regular bipartite graphs without an almost perfect matching

A graph G is close to regular or more precisely a （d, d ＋ k）-graph, if the degree of each vertex of G is between d and d ＋ k. Let d ≥ 2 be an integer, and let G be a connected bipartite （d, d＋k）-graph with partite sets X and Y such that ｜X｜- ｜Y｜＋1. If G is of order n without an almost perfect matching, then we show in this paper that·n ≥ 6d ＋7 when k = 1,·n ≥ 4d＋ 5 when k = 2,·n ≥ 4d＋3 when k≥3.Examples will demonstrate that the given bounds on the order of G are the best possible.     

Topological ordered C- (resp. I-)spaces and generalized metric spaces

The following result due to Hanai, Morita, and Stone is well known: Let f be a closed continuous map of a metric space X onto a topological space Y. Then the following statements are equivalent: (i) Y satisfies the first countability axiom; (ii) for each y∈Y, f−1{y} has a compact boundary in X; (iii) Y is metrizable.In this article we obtain several related results in the setting of topological ordered spaces. In particular we investigate the upper and lower topologies of metrizable topological ordered spaces which are both C- and I-spaces in the sense of Priestley.     

Solutions of polynomial Pell's equation

Let D=F²+2G be a monic quartic polynomial in Z[x], where . Then for F/G∈Q[x], a necessary and sufficient condition for the solution of the polynomial Pell's equation X²−DY²=1 in Z[x] has been shown. Also, the polynomial Pell's equation X²−DY²=1 has nontrivial solutions X,Y∈Q[x] if and only if the values of period of the continued fraction of are 2, 4, 6, 8, 10, 14, 18, and 22 has been shown. In this paper, for the period of the continued fraction of is 4, we show that the polynomial Pell's equation has no nontrivial solutions X,Y∈Z[x].     

Degree sum and nowhere-zero 3-flows

Let G be a simple graph on n vertices. In this paper, we prove that if G satisfies the condition that d(x)+d(y)≥n for each xy∈E(G), then G has no nowhere-zero 3-flow if and only if G is either one of the five graphs on at most 6 vertices or one of a very special class of graphs on at least 6 vertices.     

The biinvariant diagonal class for Hamiltonian torus actions

Suppose that an algebraic torus G acts algebraically on a projective manifold X with generically trivial stabilizers. Then the Zariski closure of the set of pairs {(x,y)∈X×X|y=gx for some g∈G} defines a nonzero equivariant cohomology class . We give an analogue of this construction in the case where X is a compact symplectic manifold endowed with a Hamiltonian action of a torus, whose complexification plays the role of G. We also prove that the Kirwan map sends the class [ΔG] to the class of the diagonal in each symplectic quotient. This allows to define a canonical right inverse of the Kirwan map.