A note on compact graphs

An undirected simple graph G is called compact iff its adjacency matrix A is such that the polytope S(A) of doubly stochastic matrices X which commute with A has integral-valued extremal points only. We show that the isomorphism problem for compact graphs is polynomial. Furthermore, we prove that if a graph G is compact, then a certain naive polynomial heuristic applied to G and any partner G′ decides correctly whether G and G′ are isomorphic or not. In the last section we discuss some compactness preserving operations on graphs.     

Stable 2-pairs and (X,Y)-intersection graphs

Given two fixed graphs X and Y, the (X,Y)-intersection graph of a graph G is a graph where

1. each vertex corresponds to a distinct induced subgraph in G isomorphic to Y, and

2. two vertices are adjacent iff the intersection of their corresponding subgraphs contains an induced subgraph isomorphic to X.

This notion generalizes the classical concept of line graphs since the (K₁,K₂)-intersection graph of a graph G is precisely the line graph of G.

Let ( , respectively) denote the family of line graphs of bipartite graphs (bipartite multigraphs, respectively), and refer to a pair (X,Y) as a 2-pair if Y contains exactly two induced subgraphs isomorphic to X. Then and , respectively, are the smallest families amongst the families of (X,Y)-intersection graphs defined by so called hereditary 2-pairs and hereditary non-compact 2-pairs. Furthermore, they can be characterized through forbidden induced subgraphs. With this motivation, we investigate the properties of a 2-pair (X,Y) for which the family of (X,Y)-intersection graphs coincides with (or ). For this purpose, we introduce a notion of stability of a 2-pair and obtain the desired characterization for such stable 2-pairs. An interesting aspect of the characterization is that it is based on a graph determined by the structure of (X,Y).     

Pseudo-Hamiltonian-connected graphs

Given a graph G and a positive integer k, denote by G[k] the graph obtained from G by replacing each vertex of G with an independent set of size k. A graph G is called pseudo-k Hamiltonian-connected if G[k] is Hamiltonian-connected, i.e., every two distinct vertices of G[k] are connected by a Hamiltonian path. A graph G is called pseudo Hamiltonian-connected if it is pseudo-k Hamiltonian-connected for some positive integer k. This paper proves that a graph G is pseudo-Hamiltonian-connected if and only if for every non-empty proper subset X of V(G), |N(X)|>|X|. The proof of the characterization also provides a polynomial-time algorithm that decides whether or not a given graph is pseudo-Hamiltonian-connected. The characterization of pseudo-Hamiltonian-connected graphs also answers a question of Richard Nowakowski, which motivated this paper.     

The extreme set condition of a graph

Let G be a simple graph. The size of any largest matching in G is called the matching number of G and is denoted by ν(G). Define the deficiency of G, def(G), by the equation def(G)=|V(G)|−2ν(G). A set of points X in G is called an extreme set if def(G−X)=def(G)+|X|. Let c₀(G) denote the number of the odd components of G. A set of points X in G is called a barrier if c₀(G−X)=def(G)+|X|. In this paper, we obtain the following:

(1) Let G be a simple graph containing an independent set of size i, where i2. If X is extreme in G for every independent set X of size i in G, then there exists a perfect matching in G.

(2) Let G be a connected simple graph containing an independent set of size i, where i2. Then X is extreme in G for every independent set X of size i in G if and only if G=(U,W) is a bipartite graph with |U|=|W|i, and |Γ(Y)||U|−i+m+1 for any Y U, |Y|=m (1mi−1).

(3) Let G be a connected simple graph containing an independent set of size i, where i2. Then X is a barrier in G for every independent set X of size i in G if and only if G=(U,W) is a bipartite graph with |U|=|W|=i, and |Γ(Y)|m+1 for any Y U, |Y|=m (1mi−1).     

Eulerian subgraphs containing given edges

For an integer l0, define to be the family of graphs such that if and only if for any edge subset XE(G) with |X|l, G has a spanning eulerian subgraph H with XE(H). The graphs in are known as supereulerian graphs. Let f(l) be the minimum value of k such that every k-edge-connected graph is in . Jaeger and Catlin independently proved f(0)=4. We shall determine f(l) for all values of l0. Another problem concerning the existence of eulerian subgraphs containing given edges is also discussed, and former results in [J. Graph Theory 1 (1977) 79–84] and [J. Graph Theory 3 (1979) 91–93] are extended.     

The exponent of the primitive Cayley digraphs on finite Abelian groups

Let G be finite group and let S be a subset of G. We prove a necessary and sufficient condition for the Cayley digraph X_{(G, S)} to be primitive when S contains the central elements of G. As an immediate consequence we obtain that a Cayley digraph X_{(G, S)} on an Abelian group is primitive if and only if S^−1S is a generating set for G. Moreover, it is shown that if a Cayley digraph X_{(G, S)} on an Abelian group is primitive, then its exponent either is or is not exceeding . Finally, we also characterize those Cayley digraphs on Abelian groups with exponent . In particular, we generalize a number of well-known results for the primitive circulant matrices.     

Enumeration of difference graphs

A difference graph is a bipartite graph G = (X, Y; E) such that all the neighborhoods of the vertices of X are comparable by inclusion. We enumerate labeled and unlabeled difference graphs with or without a bipartition of the vertices into two stable sets. The labeled enumerations are expressed in terms of combinatorial numbers related to the Stirling numbers of the second kind.     

The equivariant Serre spectral sequence as an application of a spectral sequence of Spanier

E.H. Spanier (1992) has constructed, for a cohomology theory defined on a triangulated space and locally constant on each open simplex, a spectral sequence whose E₂-term consists of certain simplicial cohomology groups, converging to the cohomology of the space. In this paper we study a closed G-fibration ƒ: Y → X, where G is a finite group. We show that if the base-G-spaceX is equivariantly triangulated and Y is paracompact, then Spanier's spectral sequence yields an equivariant Serre spectral sequence for ƒ. The main point here is to identify the equivariant singular cohomology groups of X with appropriate simplicial cohomology groups of the orbit space X/G.     

Projective geometries of algebraically closed fields of characteristic zero

Fix an algebraically closed field of characteristic zero and let G be its geometry of transcendence degree one extensions. Let X be a set of points of G. We show that X extends to a projective subgeometry of G exactly if the partial derivatives of the polynomials inducing dependence on its elements satisfy certain separability conditions. This analysis produces a concrete representation of the coordinatizing fields of maximal projective subgeometries of G.     

Normal Abelian subgroups and Euler characteristic

We generalize Rosset's theorem which states that the Euler characteristic of a group G of type FL_C vanishes if G contains a torsion free normal subgroup. In our case the subgroup is allowed to have torsion (but must also have elements of infinite order). Under similar conditions on the regular covering of a finite CW-complex X, it is shown that the Euler characteristic of X is 0; this includes the special case where X is nilpotent.     

Bredon-Illman cohomology with actions of totally disconnected groups

We study the Bredon-Illman cohomology with local coefficients for a G-space X in the case of G being a totally disconnected, locally compact group. We prove that any short exact sequence of equivariant local coefficients systems on X gives a long exact sequence of the associated Bredon-Illman cohomology groups with local coefficients.     

Graphs of groups and von Neumann dimension

The ℓ²-invariants of the fundamental group G of a graph of groups acting on a CW-complex X are related to the ℓ²-invariants of the edge and vertex groups of G acting on X. Various consequences are derived.     

Estimating the spectral measure of an extreme value distribution

Let (X₁, Y₁), (X₂, Y₂),…, (X_n, Y_n) be a random sample from a bivariate distribution function F which is in the domain of attraction of a bivariate extreme value distribution function G. This G is characterized by the extreme value indices and its spectral measure or angular measure. The extreme value indices determine both the marginals and the spectral measure determines the dependence structure. In this paper, we construct an empirical measure, based on the sample, which is a consistent estimator of the spectral measure. We also show for positive extreme value indices the asymptotic normality of the estimator under a suitable 2nd order strengthening of the bivariate domain of attraction condition.     

Marked length rigidity of rank one symmetric spaces and their product

In this paper we show that if two Zariski dense representations, from a group G into Iso(X) where X is rank one symmetric space, have the proportional marked length spectrum, then they are conjugate. As a generalization we show that a Zariski dense representation into the isometry group of the product of rank one symmetric spaces is determined by the marked cross ratio.     

ContributionsAcyclic graphoidal covers and path partitions in a graph

An acyclic graphoidal cover of a graph G is a collection ψ of paths in G such that every path in ψ has at least two vertices, every vertex of G is an internal vertex of at most one path in ψ and every edge of G is in exactly one path in ψ. The minimum cardinality of an acyclic graphoidal cover of G is called the acyclic graphoidal covering number of G and is denoted by η_a. A path partition of a graph G is a collection P of paths in G such that every edge of G is in exactly one path in P. The minimum cardinality of a path partition of G is called the path partition number of G and is denoted by π. In this paper we determine η_a and π for several classes of graphs and obtain a characterization of all graphs with Δ 4 and η_a = Δ − 1. We also obtain a characterization of all graphs for which η_a = π.     

Neighborhood assignments and cardinal functions: a unified approach to metrization and uniformity

We use neighborhood assignments and cardinal functions to give a unified approach to metrizability and uniformity. This leads to a number of characterizations of m(X), the metrizability degree of X, u(X), the uniform weight of X, and w(X), the weight of X. For X normal (and regular), m(X) = u(X); it is unknown whether this result extends to completely regular spaces.     

Algebraic monoids and group embeddings

We study the geometry of algebraic monoids. We prove that the group of invertible elements of an irreducible algebraic monoid is an algebraic group, open in the monoid. Moreover, if this group is reductive, then the monoid is affine. We then give a combinatorial classification of reductive monoids by means of the theory of spherical varieties. Partially supported by a CONICYT's grant and the Universidad de la República (Uruguay)     

Additive Maps Preserving Nilpotent Perturbation of Scalars

Let X be a Banach space over F(= R or C) with dimension greater than 2. Let N(X) be the set of all nilpotent operators and B_0(X) the set spanned by N(X). We give a structure result to the additive maps on FI + B_0(X) that preserve rank-1 perturbation of scalars in both directions. Based on it, a characterization of surjective additive maps on FI + B_0(X) that preserve nilpotent perturbation of scalars in both directions are obtained. Such a map Φ has the form either Φ(T) = cAT A~(-1)+ φ(T)I for all T ∈ FI + B_0(X) or Φ(T) = cAT*A~(-1)+ φ(T)I for all T ∈ FI + B_0(X), where c is a nonzero scalar,A is a τ-linear bijective transformation for some automorphism τ of F and φ is an additive functional.In addition, if dim X = ∞, then A is in fact a linear or conjugate linear invertible bounded operator.