Ternary forms as invariants of Markoff forms and other SL2 (Z)-bundles

Consider the free group Γ = {A,B} generated by matrices A, B in SL₂(Z). We can construct a ternary form Φ(x,y,z) whose GL₃(Z) equivalence class is invariant, as it depends on Γ and not the choice of generators. If Γ is the commutator of SL₂(Z), then the generating matrices have fixed points corresponding to different fields and inequivalent Markoff forms, but they are all biuniquely determined by Φ = -z²+ y(2x+y+z) to within equivalence. When referred to transformations A, B of the upper half plane, this phenomenon is interpreted in terms of inequivalent homotopy elements which are primitive for the perforated torus.     

The set of irreducible graphs for the projective plane is finite

In 1930 Kuratowski proved that a graph does not embed in the real plane R² if and only if it contains a subgraph homeomorphic to one of two graphs, K₅ or K_{3, 3}. For positive integer n, let I_n (P) denote a smallest set of graphs whose maximal valency is n and such that any graph which does not embed in the real projective plane contains a subgraph homeomorphic to a graph in I_n (P) for some n. Glover and Huneke and Milgram proved that there are only 6 graphs in I₃ (P), and Glover and Huneke proved that I_n (P) is finite for all n. This note proves that I_n (P) is empty for all but a finite number of n. Hence there is a finite set of graphs for the projective plane analogous to Kuratowski's two graphs for the plane.     

Group action for enumerating maps on surfaces

A map is a connected topological graph Γ cellularly embedded in a surface. For any connected graph Γ, by introducing the conception of semi-arc automorphism groupAut1/2 Γ and classifying all embedding of Γ under the action of this group, the numbersr ^o (Γ) andr ^N (Γ) of rooted maps on orientable and non-orientable surfaces with underlying graph Γ are found. Many closed formulas without sum Σ for the number of rooted maps on surfaces (orientable or non-orientable) with given underlying graphs, such as, complete graphK _n , complete bipartite graphK _m,n, bouquetsB _n , dipoleDp _n and generalized dipoleDp _n ^k,l are refound in this paper.     

Codes from incidence matrices of graphs

We examine the p-ary codes, for any prime p, from the row span over ${\mathbb {F}_p}$ of |V| × |E| incidence matrices of connected graphs Γ = (V, E), showing that certain properties of the codes can be directly derived from the parameters and properties of the graphs. Using the edge-connectivity of Γ (defined as the minimum number of edges whose removal renders Γ disconnected) we show that, subject to various conditions, the codes from such matrices for a wide range of classes of connected graphs have the property of having dimension |V| or |V| ? 1, minimum weight the minimum degree δ(Γ), and the minimum words the scalar multiples of the rows of the incidence matrix of this weight. We also show that, in the k-regular case, there is a gap in the weight enumerator between k and 2k ? 2 of the binary code, and also for the p-ary code, for any prime p, if Γ is bipartite. We examine also the implications for the binary codes from adjacency matrices of line graphs. Finally we show that the codes of many of these classes of graphs can be used for permutation decoding for full error correction with any information set.     

A combinatorial problem involving graphs and matrices

In this paper we discuss a combinatorial problem involving graphs and matrices. Our problem is a matrix analogue of the classical problem of finding a system of distinct representatives (transversal) of a family of sets and relates closely to an extremal problem involving 1-factors and a long standing conjecture in the dimension theory of partially ordered sets. For an integer n ?1, let n denote the n element set {1,2,3,…, n}. Then let A be a k×t matrix. We say that A satisfies property P(n, k) when the following condition is satisfied: For every k-taple (x₁,x₂,…,x_k?n^k there exist k distinct integers j₁,j₂,…,j_k so that x_i= a_ii for i= 1,2,…,k. The minimum value of t for which there exists a k × t matrix A satisfying property P(n,k) is denoted by f(n,k). For each k?1 and n sufficiently large, we give an explicit formula for f(n, k): for each n?1 and k sufficiently large, we use probabilistic methods to provide inequalities for f(n,k).     

Critical graphs,matchings and tours or a hierarchy of relaxations for the travelling salesman problem

A(perfect) 2-matching in a graphG=(V, E) is an assignment of an integer 0, 1 or 2 to each edge of the graph in such a way that the sum over the edges incident with each node is at most (exactly) two. The incidence vector of a Hamiltonian cycle, if one exists inG, is an example of a perfect 2-matching. Fork satisfying 1≦k≦|V|, we letP _k denote the problem of finding a perfect 2-matching ofG such that any cycle in the solution contains more thank edges. We call such a matching aperfect P _k -matching. Then fork<l, the problemP _k is a relaxation ofP ₁. Moreover if |V| is odd, thenP _1V1–2 is simply the problem of determining whether or notG is Hamiltonian. A graph isP _k -critical if it has no perfectP _k -matching but whenever any node is deleted the resulting graph does have one. Ifk=|V|, then a graphG=(V, E) isP _k -critical if and only if it ishypomatchable (the graph has an odd number of nodes and whatever node is deleted the resulting graph has a perfect matching). We prove the following results:

1. If a graph isP _k -critical, then it is alsoP _l -critical for all largerl. In particular, for allk, P _k -critical graphs are hypomatchable.
2. A graphG=(V, E) has a perfectP _k -matching if and only if for anyX?V the number ofP _k -critical components inG[V - X] is not greater than |X|.
3. The problemP _k can be solved in polynomial time provided we can recognizeP _k -critical graphs in polynomial time. In addition, we describe a procedure for recognizingP _k -critical graphs which is polynomial in the size of the graph and exponential ink.

     

Distance-regular graphs with girth 3 or 4: I

We study the structure of a distance-regular graph Γ with girth 3 or 4. First, we find some relationships among the intersection numbers of Γ when Γ contains a cycle {u₁, u₂, u₃, u₄} with ?(u₁, u₃) = ?(u₂, u₄) = 2. These relationships imply the diameter d, valency k, and intersection numbers a₁ and c_d of Γ are related by $\text{d ≤}\text{(k + c}{}_{\mathrm{d}}\text{)}\text{(a}{}_1\text{+ 2)}$. Next, we show subgraphs induced by vertex neighbourhoods in distance-regular graphs where cycles mentioned above do not exist are related to certain strongly regular graphs.     

Edge-colouring of graphs and hereditary graph properties

Edge-colourings of graphs have been studied for decades. We study edge-colourings with respect to hereditary graph properties. For a graph G, a hereditary graph property P and l ? 1 we define \(X{'_{P,l}}\)(G) to be the minimum number of colours needed to properly colour the edges of G, such that any subgraph of G induced by edges coloured by (at most) l colours is in P. We present a necessary and sufficient condition for the existence of \(X{'_{P,l}}\)(G). We focus on edge-colourings of graphs with respect to the hereditary properties O_k and S_k, where O_k contains all graphs whose components have order at most k+1, and S_k contains all graphs of maximum degree at most k. We determine the value of \(X{'_{{S_k},l}}(G)\) for any graph G, k ? 1, l ? 1, and we present a number of results on \(X{'_{{O_k},l}}(G)\).     

On shortest disjoint paths in planar graphs

For a graph G and a collection of vertex pairs {(s₁,t₁),…,(s_k,t_k)}, the k disjoint paths problem is to find k vertex-disjoint paths P₁,…,P_k, where P_i is a path from s_i to t_i for each i=1,…,k. In the corresponding optimization problem, the shortest disjoint paths problem, the vertex-disjoint paths P_i have to be chosen such that a given objective function is minimized. We consider two different objectives, namely minimizing the total path length (minimum sum, or short: Min-Sum), and minimizing the length of the longest path (Min-Max), for k=2,3.Min-Sum: We extend recent results by Colin de Verdière and Schrijver to prove that, for a planar graph and for terminals adjacent to at most two faces, the Min-Sum 2 Disjoint Paths Problem can be solved in polynomial time. We also prove that, for six terminals adjacent to one face in any order, the Min-Sum 3 Disjoint Paths Problem can be solved in polynomial time.Min-Max: The Min-Max 2 Disjoint Paths Problem is known to be NP-hard for general graphs. We present an algorithm that solves the problem for graphs with tree-width 2 in polynomial time. We thus close the gap between easy and hard instances, since the problem is weakly NP-hard for graphs with tree-width 3.     

The socle of the last term in a minimal injective resolution

Let Λ and Γ be left and right Noetherian rings and Λ U a generalized tilting module with Γ = End( Λ U ). For a non-negative integer k, if Λ U is (k - 2)-Gorenstein with the injective dimensions of Λ U and U Γ being k, then the socle of the last term in a minimal injective resolution of Λ U is non-zero.     

Distance-transitive representations of the symmetric groups

Let Γ be a graph and G ≤ Aut(Γ). The group G is said to act distance-transitively on Γ if, for any vertices x, y, u, v such that ∂(x, y) = ∂(u, v), there is an element g ϵ G mapping x into u and y into v. If G acts distance-transitively on Γ then the permutation group induced by the action of G on the vertex set of Γ is called the distance-transitive representation of G. In the paper all distance-transitive representations of the symmetric groups S_n are classified. Moreover, all pairs (G, Γ) such that G acts distance-transitively on Γ and G = S_n for some n are described. The classification problem for these pairs was posed by N. Biggs (Ann. N.Y. Acad. Sci. 319 (1979), 71–81). The problem is closely related to the general question about distance-transitive graphs with given automorphism group.     

Polygon-circle and word-representable graphs

We describe work on the relationship between the independently-studied polygon-circle graphs and word-representable graphs.A graph G = (V, E) is word-representable if there exists a word w over the alpha-bet V such that letters x and y form a subword of the form xyxy ⋯ or yxyx ⋯ iff xy is an edge in E. Word-representable graphs generalise several well-known and well-studied classes of graphs [S. Kitaev, A Comprehensive Introduction to the Theory of Word-Representable Graphs, Lecture Notes in Computer Science 10396 (2017) 36–67; S. Kitaev, V. Lozin, “Words and Graphs”, Springer, 2015]. It is known that any word-representable graph is k-word-representable, that is, can be represented by a word having exactly k copies of each letter for some k dependent on the graph. Recognising whether a graph is word-representable is NP-complete ([S. Kitaev, V. Lozin, “Words and Graphs”, Springer, 2015, Theorem 4.2.15]). A polygon-circle graph (also known as a spider graph) is the intersection graph of a set of polygons inscribed in a circle [M. Koebe, On a new class of intersection graphs, Ann. Discrete Math. (1992) 141–143]. That is, two vertices of a graph are adjacent if their respective polygons have a non-empty intersection, and the set of polygons that correspond to vertices in this way are said to represent the graph. Recognising whether an input graph is a polygon-circle graph is NP-complete [M. Pergel, Recognition of polygon-circle graphs and graphs of interval filaments is NP-complete, Graph-Theoretic Concepts in Computer Science: 33rd Int. Workshop, Lecture Notes in Computer Science, 4769 (2007) 238–247]. We show that neither of these two classes is included in the other one by showing that the word-representable Petersen graph and crown graphs are not polygon-circle, while the non-word-representable wheel graph W₅ is polygon-circle. We also provide a more refined result showing that for any k ≥ 3, there are k-word-representable graphs which are neither (k −1)-word-representable nor polygon-circle.     

Homogeneity conditions in graphs

Let P be a class of graphs; a graph Γ with vertex set V is locally P-homogeneous if whenever U ? V and the vertex subgraph (U) lies in P, then each automorphism of (U) extends to an automorphism of Γ. Let C be the class of connected graphs, Q the class of cones, R the class of “rakes”; we classify locally finite, locally C-homogeneous graphs, and prove that a locally finite, locally (Q ? R)-homogeneous graph is either locally C-homogeneous, or is the Levi graph of the sevenpoint projective plane.     

The iwasawa invariant μ in the composite of two Zl-extensions

Let k₀ be a finite extension field of the rational numbers, and assume k₀ has at least two Z_l-extensions. Assume that at least one Z_l-extension $\text{K}\text{k}{}_0$ has Iwasawa invariant μ = 0, and let L be the composite of K and some other Z_l-extension of k₀. In this paper we find an upper bound for the number of Z_l-extensions of k₀ contained in L with nonzero μ.     

Characterizations of restricted pairs of planar graphs allowing simultaneous embedding with fixed edges

A set of planar graphs {G₁(V,E₁),…,Gk(V,Ek)} admits a simultaneous embedding if they can be drawn on the same pointset P of order n in the Euclidean plane such that each point in P corresponds one-to-one to a vertex in V and each edge in Ei does not cross any other edge in Ei (except at endpoints) for i∈{1,…,k}. A fixed edge is an edge (u,v) that is drawn using the same simple curve for each graph Gi whose edge set Ei contains the edge (u,v). We give a necessary and sufficient condition for two graphs whose union is homeomorphic to K₅ or K3,3 to admit a simultaneous embedding with fixed edges (SEFE). This allows us to characterize the class of planar graphs that always have a SEFE with any other planar graph. We also characterize the class of biconnected outerplanar graphs that always have a SEFE with any other outerplanar graph. In both cases, we provide O(n⁴)-time algorithms to compute a SEFE.     

Graphs with bounded valency that do not embed in the projective plane

In 1930 Kuratowski proved that a graph does not embed in the real plane R² if and only if it contains a subgraph homeomorphic to one of two graphs, K₅ or K₃₃. Let I_n(P) denote the minimal set of graphs whose vertices have miximal valency n such that any graph which does not embed in the real projective plane (or equivalently, does not embed in the Möbius band) contains a subgraph homeomorphic to a graph in I_n(P) for some positive integer n. Glover and Huneke and Milgram proved that there are only 6 graphs in I₃(P). This note proves that for each n, I_n(P) is finite.     

The non-gap sequence of a subcode of a generalized Reed–Solomon code

This paper addresses the question how often the square code of an arbitrary l-dimensional subcode of the code GRS _k (a, b) is exactly the code GRS_2k-1(a, b * b). To answer this question we first introduce the notion of gaps of a code which allows us to characterize such subcodes easily. This property was first used and stated by Wieschebrink where he applied the Sidelnikov–Shestakov attack to break the Berger–Loidreau cryptosystem.     

Path Ramsey numbers in multicolorings

In this paper we consider the general Ramsey number problem for paths when the complete graph is colored with k colors. Specifically, given paths P_i1, P_i2,…, P_ik with i₁, i₂,…, i_k vertices, we determine for certain i_j (1 ≤ j ≤ k) the smallest positive integer n such that a k coloring of the complete graph K_n contains, for some l, a P_il in the lth color. For k = 3, given i₂, i₃, the problem is solved for all but a finite number of values of i₁. The procedure used in the proof uses an improvement of an extremal theorem for paths by P. Erdös and T. Gallai.     

Super cyclically edge-connected vertex-transitive graphs of girth at least 5

A cyclic edge-cut of a graph G is an edge set, the removal of which separates two cycles. If G has a cyclic edge-cut, then it is called cyclically separable. We call a cyclically separable graph super cyclically edge-connected, in short, super-λc, if the removal of any minimum cyclic edge-cut results in a component which is a shortest cycle. In [Zhang, Z., Wang, B.: Super cyclically edge-connected transitive graphs. J. Combin. Optim., 22, 549-562 (2011)], it is proved that a connected vertex-transitive graph is super-λc if G has minimum degree at least 4 and girth at least 6, and the authors also presented a class of nonsuper-λc graphs which have degree 4 and girth 5. In this paper, a characterization of k (k≥4)-regular vertex-transitive nonsuper-λc graphs of girth 5 is given. Using this, we classify all k (k≥4)-regular nonsuper-λc Cayley graphs of girth 5, and construct the first infinite family of nonsuper-λc vertex-transitive non-Cayley graphs.     

Familles de graphes expanseurs et paires de HeckeFamilies of expanding graphs and Hecke pairs

Let H be a subgroup of a group G. Suppose that (G,H) is a Hecke pair and that H is finitely generated by a finite symmetric set of size k. Then G/H can be seen as a graph (possibly with loops and multiple edges) whose connected components form a family (X_i)_i∈I of finite k-regular graphs. In this Note, we analyse when the size of these graphs is bounded or tends to infinity and we present criteria for (X_i)_i∈I to be a family of expanding graphs as well as some examples. To cite this article: M.B. Bekka et al., C. R. Acad. Sci. Paris, Ser. I 335 (2002) 463–468.