Graphs with independent perfect matchings

A graph with at least two vertices is matching covered if it is connected and each edge lies in some perfect matching. A matching covered graph G is extremal if the number of perfect matchings of G is equal to the dimension of the lattice spanned by the set of incidence vectors of perfect matchings of G. We first establish several basic properties of extremal matching covered graphs. In particular, we show that every extremal brick may be obtained by splicing graphs whose underlying simple graphs are odd wheels. Then, using the main theorem proved in 2 and 3 , we find all the extremal cubic matching covered graphs. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 19–50, 2005     

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.     

Normal subgroups of infinite multiply transitive permutation groups

Some generalisations to infinite permutation groups of familiar results on normal subgroups of finite multiply transitive permutation groups are given, and the limits of these results are explored by means of examples.     

Transformation of incidence structures and sharply multiply transitive permutation sets

In this note we generalize the transformation process introduced in [8]. This generalization allows to find the nonplanar nearfield discovered by H.Karzel and W.Kerby, [5], [6], and the affine Andrè planes.Dedicated to Prof. A.Barlotti and to Prof. L.A.Rosati on their 70th birthdayWork performed under the auspicies of G.N.S.A.G.A. and supported by 40% grants of M.U.R.S.T.     

Graphs whose every transitive orientation contains almost every relation

Given a graphG onn vertices and a total ordering ≺ ofV(G), the transitive orientation ofG associated with ≺, denotedP(G; ≺), is the partial order onV(G) defined by settingx<y inP(G; ≺) if there is a pathx=x ₁ x ₂…x _r=y inG such thatx ₁ ≺x _j for 1≦i<j≦r. We investigate graphsG such that every transitive orientation ofG contains ₂ ⁿ −o(n ²) relations. We prove that almost everyG _n,p satisfies this requirement if , but almost noG _n,p satisfies the condition if (pn log log logn)/(logn log logn) is bounded. We also show that every graphG withn vertices and at mostcn logn edges has some transitive orientation with fewer than ₂ ⁿ −δ(c)n ² relations. Partially supported by MCS Grant 8104854.     

Homogeneous curves that contain arcs

The author has classified atriodic, homogeneous, one-dimensional continua that contain arcs— they are precisely the solenoids. This paper begins the study of homogeneous, one-dimensional continua that contain an arc and a triod.     

Topologically transitive subsets of piecewise monotonic maps,which contain no periodic points

If one splits the nonwandering set of a piecewise monotonic map into maximal subsets, which are topologically transitive, one gets two kinds of subsets. The first kind of these subsets has periodic orbits dense, the second kind contains no periodic orbits. In this paper it is shown, that there are only finitely many subsets of the second kind, each of which is minimal and has only finitely many ergodic invariant Borel probability measures.     

Graphs that are not complete pluripolar

Let be domains in . Under very mild conditions on we show that there exist holomorphic functions , defined on with the property that is nowhere extendible across , while the graph of over is not complete pluripolar in . This refutes a conjecture of Levenberg, Martin and Poletsky (1992).

     

On distance-3 matchings and induced matchings

For a finite undirected graph G=(V,E) and positive integer k≥1, an edge set M⊆E is a distance-k matching if the pairwise distance of edges in M is at least k in G. For k=1, this gives the usual notion of matching in graphs, and for general k≥1, distance-k matchings were called k-separated matchings by Stockmeyer and Vazirani. The special case k=2 has been studied under the names induced matching (i.e., a matching which forms an induced subgraph in G) by Cameron and strong matching by Golumbic and Laskar in various papers.Finding a maximum induced matching is NP-complete even on very restricted bipartite graphs and on claw-free graphs but it can be done efficiently on various classes of graphs such as chordal graphs, based on the fact that an induced matching in G corresponds to an independent vertex set in the square L(G)² of the line graph L(G) of G which, by a result of Cameron, is chordal for any chordal graph G.We show that, unlike for k=2, for a chordal graph G, L(G)³ is not necessarily chordal, and finding a maximum distance-3 matching, and more generally, finding a maximum distance-(2k+1) matching for k≥1, remains NP-complete on chordal graphs. For strongly chordal graphs and interval graphs, however, the maximum distance-k matching problem can be solved in polynomial time for every k≥1. Moreover, we obtain various new results for maximum induced matchings on subclasses of claw-free graphs.     

Graphs that admit right angle crossing drawings

We consider right angle crossing (RAC) drawings of graphs in which the edges are represented by polygonal arcs and any two edges can cross only at a right angle. We show that if a graph with n vertices admits a RAC drawing with at most 1 bend or 2 bends per edge, then the number of edges is at most 6.5n and 74.2n, respectively. This is a strengthening of a recent result of Didimo et al.     

Subgroups of symplectic groups that contain a subsystem subgroup

Let Γ = GSp(2l, R) be the general symplectic group of rank l over a commutative ring R such that 2 ∈ R*; and let ν be a symmetric equivalence relation on the index set {1,…, l, −l,…, 1} all of whose classes contain at least 3 elements. In the present paper, we prove that if a subgroup H of Γ contains the group E_Γ(ν) of elementary block diagonal matrices of type ν, then H normalizes the subgroup generated by all elementary symplectic transvections T_ij(ξ) ∈ H. Combined with the previous results, this completely describes the overgroups of subsystem subgroups in this case. Similar results for subgroups of GL(n, R) were established by Z. I. Borewicz and the author in the early 1980s, while for GSp(2l, R) and GO(n, R) they have been announced by the author in the late 1980s, but a complete proof for the symplectic case has not been published before. Bibliography: 74 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 349, 2007, pp. 5–29.     

A manifold that does not contain a compact core

A core of a (noncompact) manifold is a submanifold with the property that the inclusion of the submanifold into the manifold is a homotopy equivalence. It is shown by example that a manifold may fail to contain a compact core even though the manifold has the homotopy type of a finite complex.     

On optimal matchings

Givenn random red points on the unit square, the transportation cost between them is tipically √n logn.