A Wilson group of non-uniformly exponential growth

This Note constructs a finitely generated group W whose word-growth is exponential, but for which the infimum of the growth rates over all finite generating sets is 1 – in other words, of non-uniformly exponential growth.This answers a question by Mikhael Gromov (Structures métriques pour les variétés riemanniennes, in: J. Lafontaine, P. Pansu (Eds.), CEDIC, Paris, 1981).The construction also yields a group of intermediate growth V that locally resembles W in that (by changing the generating set of W) there are isomorphic balls of arbitrarily large radius in V and W's Cayley graphs. To cite this article: L. Bartholdi, C. R. Acad. Sci. Paris, Ser. I 336 (2003).     

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.     

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.     

3-Factor-criticality in domination critical graphs

A graph G is said to be k-γ-critical if the size of any minimum dominating set of vertices is k, but if any edge is added to G the resulting graph can be dominated with k-1 vertices. The structure of k-γ-critical graphs remains far from completely understood when k?3.A graph G is factor-critical if G-v has a perfect matching for every vertex v∈V(G) and is bicritical if G-u-v has a perfect matching for every pair of distinct vertices u,v∈V(G). More generally, a graph is said to be k-factor-critical if G-S has a perfect matching for every set S of k vertices in G. In three previous papers [N. Ananchuen, M.D. Plummer, Some results related to the toughness of 3-domination-critical graphs, Discrete Math. 272 (2003) 5-15; N. Ananchuen, M.D. Plummer, Matching properties in domination critical graphs, Discrete Math. 277 (2004) 1-13; N. Ananchuen, M.D. Plummer, Some results related to the toughness of 3-domination-critical graphs. II. Utilitas Math. 70 (2006) 11-32], we explored the toughness of 3-γ-critical graphs and some of their matching properties. In particular, we obtained some properties which are sufficient for a 3-γ-critical graph to be factor-critical and, respectively, bicritical. In the present work, we obtain similar results for k-factor-critical graphs when k=3.     

Removable edges in a 5-connected graph and a construction method of 5-connected graphs

An edge e of a k-connected graph G is said to be a removable edge if G?e is still k-connected. A k-connected graph G is said to be a quasi (k+1)-connected if G has no nontrivial k-separator. The existence of removable edges of 3-connected and 4-connected graphs and some properties of quasi k-connected graphs have been investigated [D.A. Holton, B. Jackson, A. Saito, N.C. Wormale, Removable edges in 3-connected graphs, J. Graph Theory 14(4) (1990) 465-473; H. Jiang, J. Su, Minimum degree of minimally quasi (k+1)-connected graphs, J. Math. Study 35 (2002) 187-193; T. Politof, A. Satyanarayana, Minors of quasi 4-connected graphs, Discrete Math. 126 (1994) 245-256; T. Politof, A. Satyanarayana, The structure of quasi 4-connected graphs, Discrete Math. 161 (1996) 217-228; J. Su, The number of removable edges in 3-connected graphs, J. Combin. Theory Ser. B 75(1) (1999) 74-87; J. Yin, Removable edges and constructions of 4-connected graphs, J. Systems Sci. Math. Sci. 19(4) (1999) 434-438]. In this paper, we first investigate the relation between quasi connectivity and removable edges. Based on the relation, the existence of removable edges in k-connected graphs (k?5) is investigated. It is proved that a 5-connected graph has no removable edge if and only if it is isomorphic to K₆. For a k-connected graph G such that end vertices of any edge of G have at most k-3 common adjacent vertices, it is also proved that G has a removable edge. Consequently, a recursive construction method of 5-connected graphs is established, that is, any 5-connected graph can be obtained from K₆ by a number of θ⁺-operations. We conjecture that, if k is even, a k-connected graph G without removable edge is isomorphic to either K_k+1 or the graph H_k/2+1 obtained from K_k+2 by removing k/2+1 disjoint edges, and, if k is odd, G is isomorphic to K_k+1.     

Matching properties in connected domination critical graphs

A dominating set of vertices S of a graph G is connected if the subgraph G[S] is connected. Let γ_c(G) denote the size of any smallest connected dominating set in G. A graph G is k-γ-connected-critical if γ_c(G)=k, but if any edge is added to G, then γ_c(G+e)?k-1. This is a variation on the earlier concept of criticality of edge addition with respect to ordinary domination where a graph G was defined to be k-critical if the domination number of G is k, but if any edge is added to G, the domination number falls to k-1.A graph G is factor-critical if G-v has a perfect matching for every vertex v∈V(G), bicritical if G-u-v has a perfect matching for every pair of distinct vertices u,v∈V(G) or, more generally, k-factor-critical if, for every set S⊆V(G) with |S|=k, the graph G-S contains a perfect matching. In two previous papers [N. Ananchuen, M.D. Plummer, Matching properties in domination critical graphs, Discrete Math. 277 (2004) 1-13; N. Ananchuen, M.D. Plummer, 3-factor-criticality in domination critical graphs, Discrete Math. 2007, to appear [3].] on ordinary (i.e., not necessarily connected) domination, the first and third authors showed that under certain assumptions regarding connectivity and minimum degree, a critical graph G with (ordinary) domination number 3 will be factor-critical (if |V(G)| is odd), bicritical (if |V(G)| is even) or 3-factor-critical (again if |V(G)| is odd). Analogous theorems for connected domination are presented here. Although domination and connected domination are similar in some ways, we will point out some interesting differences between our new results for the case of connected domination and the results in [N. Ananchuen, M.D. Plummer, Matching properties in domination critical graphs, Discrete Math. 277 (2004) 1-13; N. Ananchuen, M.D. Plummer, 3-factor-criticality in domination critical graphs, Discrete Math. 2007, to appear [3].].     

Competitively Tight Graphs

The competition graph of a digraph D is a (simple undirected) graph which has the same vertex set as D and has an edge between two distinct vertices x and y if and only if there exists a vertex v in D such that (x, v) and (y, v) are arcs of D. For any graph G, G together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number k(G) of a graph G is the smallest number of such isolated vertices. Computing the competition number of a graph is an NP-hard problem in general and has been one of the important research problems in the study of competition graphs. Opsut [1982] showed that the competition number of a graph G is related to the edge clique cover number θ _E (G) of the graph G via θ _E (G) ? |V(G)| + 2 ≤ k(G) ≤ θ _E (G). We first show that for any positive integer m satisfying 2 ≤ m ≤ |V(G)|, there exists a graph G with k(G) = θ _E (G) ? |V(G)| + m and characterize a graph G satisfying k(G) = θ _E (G). We then focus on what we call competitively tight graphs G which satisfy the lower bound, i.e., k(G) = θ _E (G) ? |V(G)| + 2. We completely characterize the competitively tight graphs having at most two triangles. In addition, we provide a new upper bound for the competition number of a graph from which we derive a sufficient condition and a necessary condition for a graph to be competitively tight.     

Hamiltonian cycles in generalized petersen graphs

Watkins (J. Combinatorial Theory 6 (1969), 152–164) introduced the concept of generalized Petersen graphs and conjectured that all but the original Petersen graph have a Tait coloring. Castagna and Prins (Pacific J. Math. 40 (1972), 53–58) showed that the conjecture was true and conjectured that generalized Petersen graphs G(n, k) are Hamiltonian unless isomorphic to G(n, 2) where n ≡ 5(mod 6). The purpose of this paper is to prove the conjecture of Castagna and Prins in the case of coprime numbers n and k.     

Graph parameters measuring neighbourhoods in graphs—Bounds and applications

The neighbourhood-width of a graph G=(V,E) is introduced in [F. Gurski, Linear layouts measuring neighbourhoods in graphs, Discrete Math. 306 (15) (2006) 1637-1650.] as the smallest integer k such that there is a linear layout ?:V→{1,…,|V|} such that for every 1?i<|V| the vertices u with ?(u)?i can be divided into at most k subsets each members having the same neighbours with respect to the vertices v with ?(v)>i.In this paper we show first bounds for the neighbourhood-width of general graphs, caterpillars, trees and grid graphs and give applications of the layout parameter neighbourhood-width in graph drawing and VLSI design.     

The dynamics of the line and path graph operators

For any integerk e 1 thek- path graph P_k (G) of a graph G has all length-k subpaths ofG as vertices, and two such vertices are adjacent whenever their union (as subgraphs ofG) forms a path or cycle withk + 1 edges. Fork = 1 we get the well-known line graphP ₁ (G) =L(G). Iteratedk-path graphs P^t _k(G) are defined as usual by P^t _k (G) := P_k(P ^t?1 _k(G)) ift < 1, and by P¹ _k(G): = P_k(G). A graph G isP _k -periodic if it is isomorphic to some iteratedk-path graph of itself; itP _k -converges if some iteratedk-path graph of G isP _k -periodic. A graph has infiniteP _k -depth if for any positive integert there is a graphH such that P^t _k(H) ?G. In this paperP _k -periodic if it is isomorphic to some iteratedk-path graph of itself; itP _k -converges if some iteratedk-path graph of G isP _k -periodic graphs,P _k -periodic if it is isomorphic to some iteratedk-path graph of itself; itP _k -converges if some iteratedk-path graph of G isP _k -convergent graphs, and graphs with infiniteP _k -periodic if it is isomorphic to some iteratedk-path graph of itself; itP _k -converges if some iteratedk-path graph of G isP _k -depth are characterized inside some subclasses of the class of locally finite graphs fork = 1, 2.     

Sur la répartition des diamants dans un tournoi

A tournament T=(V,A) is a directed graph such that for every x,y∈V, where x≠y, (x,y)∈A if and only if (y,x)?A. For example, the 3-cycle is the tournament ({1,2,3}, {(1,2),(2,3),(3,1)}). Up to an isomorphism, there are two tournaments with 4 vertices and containing an unique 3-cycle which we call diamonds. We prove that for any tournament T defined on n?9 vertices, either T contains at least 2n?6 diamonds or the number of diamonds contained in T is equal to 0, n?3 or 2n?8. Following the characterization of the tournaments without diamonds due to Gnanvo and Ille (Z. Math. Logik Grundlag. Math. 38 (1992) 283–291) and to Lopez and Rauzy (Z. Math. Logik Grundlag. Math. 38 (1992) 27–37), we study the morphology of the tournaments defined on n?5 vertices and which contain exactly n?3 or 2n?8 diamonds. To cite this article: H. Bouchaala, C. R. Acad. Sci. Paris, Ser. I 338 (2004).     

A note on Roman domination in graphs

Let G=(V,E) be a simple graph. A subset S⊆V is a dominating set of G, if for any vertex u∈V-S, there exists a vertex v∈S such that uv∈E. The domination number of G, γ(G), equals the minimum cardinality of a dominating set. A Roman dominating function on graph G=(V,E) is a function f:V→{0,1,2} satisfying the condition that every vertex v for which f(v)=0 is adjacent to at least one vertex u for which f(u)=2. The weight of a Roman dominating function is the value f(V)=∑_v∈Vf(v). The Roman domination number of a graph G, denoted by γ_R(G), equals the minimum weight of a Roman dominating function on G. In this paper, for any integer k(2?k?γ(G)), we give a characterization of graphs for which γ_R(G)=γ(G)+k, which settles an open problem in [E.J. Cockayne, P.M. Dreyer Jr, S.M. Hedetniemi et al. On Roman domination in graphs, Discrete Math. 278 (2004) 11-22].     

On k-graceful,locally finite graphs

While a finite, bipartite graph G can be k-graceful for every k ≥ 1, a finite nonbipartite G can be k-graceful for only finitely many values of k. An improved bound on such possible values of k is presented. Definitions are extended to infinite graphs, and it is shown that if G is locally finite and vertex set V(G) and edge set E(G) are countably infinite, then for each k ≥ 1 the graph G has a k-graceful numbering h mapping V(G) onto the set of nonnegative integers.     

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.     

Nordhaus-Gaddum results for restrained domination and total restrained domination in graphs

Let G=(V,E) be a graph. A set S⊆V is a total restrained dominating set if every vertex is adjacent to a vertex in S and every vertex of V-S is adjacent to a vertex in V-S. A set S⊆V is a restrained dominating set if every vertex in V-S is adjacent to a vertex in S and to a vertex in V-S. The total restrained domination number of G (restrained domination number of G, respectively), denoted by γ_tr(G) (γ_r(G), respectively), is the smallest cardinality of a total restrained dominating set (restrained dominating set, respectively) of G. We bound the sum of the total restrained domination numbers of a graph and its complement, and provide characterizations of the extremal graphs achieving these bounds. It is known (see [G.S. Domke, J.H. Hattingh, S.T. Hedetniemi, R.C. Laskar, L.R. Markus, Restrained domination in graphs, Discrete Math. 203 (1999) 61-69.]) that if G is a graph of order n?2 such that both G and are not isomorphic to P₃, then . We also provide characterizations of the extremal graphs G of order n achieving these bounds.     

On minimally circular-imperfect graphs

A circular-perfect graph is a graph of which each induced subgraph has the same circular chromatic number as its circular clique number. In this paper, (1) we prove a lower bound on the order of minimally circular-imperfect graphs, and characterize those that attain the bound; (2) we prove that if G is a claw-free minimally circular-imperfect graph such that ω_c(G-x)>ω(G-x) for some x∈V(G), then G=K_(2k+1)/2+x for an integer k; and (3) we also characterize all minimally circular-imperfect line graphs.     

Rooted directed path graphs are leaf powers

Leaf powers are a graph class which has been introduced to model the problem of reconstructing phylogenetic trees. A graph G=(V,E) is called k-leaf power if it admits a k-leaf root, i.e., a tree T with leaves V such that uv is an edge in G if and only if the distance between u and v in T is at most k. Moroever, a graph is simply called leaf power if it is a k-leaf power for some k∈N. This paper characterizes leaf powers in terms of their relation to several other known graph classes. It also addresses the problem of deciding whether a given graph is a k-leaf power.We show that the class of leaf powers coincides with fixed tolerance NeST graphs, a well-known graph class with absolutely different motivations. After this, we provide the largest currently known proper subclass of leaf powers, i.e, the class of rooted directed path graphs.Subsequently, we study the leaf rank problem, the algorithmic challenge of determining the minimum k for which a given graph is a k-leaf power. Firstly, we give a lower bound on the leaf rank of a graph in terms of the complexity of its separators. Secondly, we use this measure to show that the leaf rank is unbounded on both the class of ptolemaic and the class of unit interval graphs. Finally, we provide efficient algorithms to compute 2|V|-leaf roots for given ptolemaic or (unit) interval graphs G=(V,E).     

On multiple sum and product sets of finite sets of integers

Let $\text{A?}\text{Z}$ be a finite set of integers of cardinality |A|=N?2. Given a positive integer k, denote kA (resp. A^(k)) the set of all sums (resp. products) of k elements of A. We prove that for all b>1, there exists k=k(b) such that max(|kA|,|A^(k)|)>N^b. This answers affirmably questions raised in Erd?s and Szemerédi (Stud. Pure Math., 1983, pp. 213–218), Elekes et al. (J. Number Theory 83 (2) (2002) 194–201) and recently, by S. Konjagin (private communication). The method is based on harmonic analysis techniques in the spirit of Chang (Ann. Math. 157 (2003) 939–957) and combinatorics on graphs. To cite this article: J. Bourgain, M.-C. Chang, C. R. Acad. Sci. Paris, Ser. I 337 (2003).     

Sur la catégorie Db,G(X) pour G réductif fini

In this Note, we are interested in the G-equivariant derived category of a smooth projective scheme over an algebraically closed field k, on which a reductive finite group G is acting. We compare the G-equivariant derived category of X with the derived category of the quotient by giving a descent criterion. The result generalizes a theorem of Lønsted in G-equivariant K-theory on curves (K. Lønsted, J. Math. Kyoto Univ. 23 (4) (1983) 775–793). We also give an equivariant version of Be??linson's equivalence of categories (Funct. Anal. Appl. 12 (1979) 214–216) and treat the exemple of the projective line. To cite this article: S. Térouanne, C. R. Acad. Sci. Paris, Ser. I 336 (2003).     

The Harary index of ordinary and generalized quasi-tree graphs

The Harary index is defined as the sum of reciprocals of distances between all pairs of vertices of a connected graph. The quasi-tree graph is a graph G in which there exists a vertex v∈V(G) such that G?v is a tree. In this paper, we presented the upper and lower bounds on the Harary index of all quasi-tree graphs of order n and characterized the corresponding extremal graphs. Moreover we defined the k-generalized quasi-tree graph to be a connected graph G with a subset V _k ?V(G) where |V _k |=k such that G?V _k is a tree. And we also determined the k-generalized quasi-tree graph of order n with maximal Harary index for all values of k and the extremal one with minimal Harary index for k=2.