The independence graph of a finite group
- PDF / 304,455 Bytes
- 12 Pages / 439.37 x 666.142 pts Page_size
- 56 Downloads / 207 Views
The independence graph of a finite group Andrea Lucchini1 Received: 12 May 2020 / Accepted: 16 July 2020 © The Author(s) 2020
Abstract Given a finite group G, we denote by (G) the graph whose vertices are the elements G and where two vertices x and y are adjacent if there exists a minimal generating set of G containing x and y. We prove that (G) is connected and classify the groups G for which (G) is a planar graph. Keywords Generating sets · Generating graph · Connectivity · Planarity · Soluble groups Mathematics Subject Classification 20D60 · 05C25
1 Introduction The generating graph of a finite group G is the graph defined on the elements of G in such a way that two distinct vertices are connected by an edge if and only if they generate G. It was defined by Liebeck and Shalev in [14], and has been further investigated by many authors: see for example [5,7,9,10,13,17,20–22] for some of the range of questions that have been considered. Clearly the generating graph of G is an edgeless graph if G is not 2-generated. We propose and investigate a possible generalization, that gives useful information even when G is not 2-generated. Let G be a finite group. A generating set X of G is said to be minimal if no proper subset of X generates G. We denote by (G) the graph whose vertices are the elements of G and in which two vertices x and y are joined by an edge if and only if x = y and there exists a minimal generating set of G containing x and y. Roughly speaking, x and y are adjacent vertices of (G) is they are ‘independent’, so we call (G) the independence graph of G. We will denote by V (G) the set of the non-isolated vertices
Communicated by Adrian Constantin.
B 1
Andrea Lucchini [email protected] Dipartimento di Matematica “Tullio Levi-Civita”, Università degli Studi di Padova, Via Trieste 63, 35121 Padua, Italy
123
A. Lucchini
of (G) and by (G) the subgraph of (G) induced by V (G). Our main result is the following. Theorem 1 If G is a finite group, then the graph (G) is connected. We prove a stronger result in the case of finite soluble groups. For a positive integer u, we denote by u (G) the subgraph of (G) in which x and y are joined by an edge if and only if there exists a minimal generating set of size u containing x and y. As before, we denote by u (G) the subgraph of u (G) induced by the set Vu (G) of its non-isolated vertices. Notice that, even when G is u-generated, the set Vu (G) is in general different from V (G). For example if G = Sym(4), then {(1, 2)(3, 4), (1, 2), (1, 2, 3)} is a minimal generating set for G, so (1, 2)(3, 4) ∈ V (G); however (1, 2)(3, 4) ∈ / V2 (G). If G is a non-cyclic 2-generated group, then 2 (G) coincides with the generating graph of G and it follows from [10, Theorem 1] that 2 (G) is a connected graph if G is soluble. We generalize this result in the following way. Theorem 2 If u ∈ N and G is a finite soluble group, then u (G) is connected. Recall that a graph is said to be embeddable in the plane, or planar, if it can be drawn in the plane so that i
Data Loading...
