/^creative ^commor
ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 13 (2017) 293-306
Uniformly dissociated graphs*
Boštjan Brešar t
Faculty of Natural Sciences and Mathematics, University of Maribor, Koroška cesta 160, Maribor, Slovenia
Bert L. Hartnell
Department of Mathematics and Computing Science, Saint Mary's University, Halifax, Nova Scotia, B3H 3C3, Canada
Douglas F. Rail *
Department of Mathematics, Furman University, Greenville, SC, USA Received 11 January 2016, accepted 2 March 2017, published online 9 March 2017
Abstract
A set D of vertices in a graph G is called a dissociation set if every vertex in D has at most one neighbor in D. We call a graph G uniformly dissociated if all maximal dissociation sets are of the same cardinality. Characterizations of uniformly dissociated graphs with small cardinalities of dissociation sets are proven; in particular, the graphs in which all maximal dissociation sets are of cardinality 2 are the complete graphs on at least two vertices from which possibly a matching is removed, while the graphs in which all maximal dissociation sets are of cardinality 3 are the complements of the K4-free geodetic graphs with diameter 2. A general construction by which any graph can be embedded as an induced subgraph of a uniformly dissociated graph is also presented. In the main result we characterize uniformly dissociated graphs with girth at least 7 to be either isomorphic to C7, or obtainable from an arbitrary graph H with girth at least 7 by identifying each vertex of H with a leaf of a copy of P3.
Keywords: Dissociation number, well-covered graphs, girth, Moore graph, polarity graph. Math. Subj. Class.: 05C69, 05C70, 05C75
*	The second and the third author gratefully acknowledge the support of the project "Internationalisation - a pillar of development of the University of Maribor."
t Corresponding author. The author acknowledges the financial support from the Slovenian Research Agency (research core funding No. P1-0297 and project grant J1-7110). The author is also affiliated with the Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia.
*	The work of this author was partially supported by a grant from the Simons Foundation (#209654 to Douglas F. Rall).
E-mail addresses: bostjan.bresar@um.si (Boštjan Brešar), bert.hartnell@smu.ca (Bert L. Hartnell), doug.rall@furman.edu (Douglas F. Rall)
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
294
Ars Math. Contemp. 13 (2017) 293-306
1 Introduction
A set D of vertices in a graph G is called a dissociation set if the subgraph induced by vertices of D has maximum degree at most 1. The cardinality of a maximum dissociation set D in a graph G is called the dissociation number of G, and is denoted by diss(G). The dissociation number was introduced by Papadimitriou and Yannakakis [14] in relation with the complexity of the so-called restricted spanning tree problem. Another closely related concept is the k-path vertex cover, which was introduced in [5] and studied in several papers [4, 10]; the corresponding invariant, the k-path vertex cover number of an arbitrary graph G, is denoted by (G). As it turns out, dissociation sets are complements of 3-path vertex covers of G, and so the following relation holds:
diss(G) = |V(G)| - ^3(G),
where ^3(G) is the size of a minimum 3-path vertex cover. The decision version of the k-path vertex cover number is NP-complete [5], moreover, in the case k = 3 it is NP-complete even in bipartite graphs which are C4-free and have maximum degree 3 [2]; cf. also [13] for further strengthening of this result and [12] for an approximation algorithm.
Are there any graphs in which the dissociation number is easily computable? The approach taken in this paper will be similar to the one related to well-covered graphs, as introduced by Plummer in 1970 [15]. These are the graphs in which every maximal independent set of vertices is of the same size, and hence maximum. Whereas determining the independence number of an arbitrary graph is also NP-complete, it is easy for a well-covered graph since a greedy algorithm will produce the desired result. One approach to deciding if a graph is well-covered has been to restrict the girth [7]. We shall employ that technique in this paper and characterize the graphs of girth 7 or more in which every maximal dissociation set is maximum. Such an approach has been used also on other similar problems, notably the limited packing problem [8] and equipackable graphs [9].
We say that a graph G is a uniformly dissociated graph if all maximal dissociation sets are of the same size; in other words, every maximal dissociation set in G is of cardinality diss (G). In particular, this implies that a greedy algorithm, in which vertices are being added to the set, taking care that a newly added vertex is adjacent to at most one vertex of degree 0 and to no vertex of degree 1 in the subgraph induced by the previously added vertices, at the end always gives a dissociation set of maximum cardinality.
The paper is organized as follows. In the next section we study the uniformly dissociated graphs whose maximal dissociation sets are of cardinalities 1, 2 or 3. For the latter class of graphs we present two characterizations, one of which states that they are precisely the complements of the K4-free geodetic graphs with diameter 2 (geodetic graphs with diameter 2 have been studied in several papers, and in the triangle-free case coincide with the well-known Moore graphs; graphs in this class that have triangles include another known family—the polarity graphs). In Section 3 we introduce the concept of extendable vertices with respect to uniformly dissociated graphs, by following a similar approach as is known for building bigger well-covered graphs using extendable vertices with respect to the well-covered notion. We prove that from an arbitrary graph G by attaching an extendable vertex of a uniformly dissociated graph to each vertex of G one obtains a uniformly dissociated graph. Section 4 contains our main result, a characterization of uniformly dissociated graphs with girth at least 7. Notably, they are precisely the graphs of which each connected component is either isomorphic to C7, or can be obtained from an arbitrary con-
B. Bresar et al.: Uniformly dissociated graphs
295
nected graph H with girth at least 7, by identifying each vertex of H with a leaf of a copy of P3.
We conclude this section by presenting the notation used throughout the paper.
Let G be a graph and S c V(G). We write G[S] for the subgraph of G induced by S and write G - S for the subgraph of G induced by the set V(G) \ S. On the other hand, if F c E(G), then G - F is the subgraph of G obtained from G by removing the edges of F. Let NG (v) denote the (open) neighborhood in G of a vertex v, while NG [v] = NG (v) U {v} is its closed neighborhood in G. When the graph G is clear from the context we omit the subscript. If S c V(G), then NG [S] = |Jv£S NG [v]. The degree of a vertex v is defined to be |NG(v)|. We call a vertex of degree 1 a leaf, while the neighbor of a leaf will be called a stem. A matching M in a graph G is a set of edges in G having the property that no two edges in M have a common endvertex. Given a matching M in G, we denote by V(M) the set of endvertices of edges from M. Recall that a matching M is an induced matching if the only edges in G[V (M)] are the edges in M itself. We denote the cardinality of the largest independent set of vertices by a(G). The girth, g(G), is the length of a shortest cycle in G. Given a graph G, the complement of G is the graph G that has the same vertex set as G, while the edge set of G is the complement of the edge set of G.
2 Classes of uniformly dissociated graphs
Let Dk be the set of uniformly dissociated graphs G such that diss (G) = k. Suppose that G € Dk and that H is an induced subgraph of G. Since any dissociation set of H is also a dissociation set of G, it follows that diss(H) < k. However, it need not be the case that H € Dk. For example, the path P4 is an induced subgraph of C5 and C5 € D3, but P4 has maximal dissociation sets of orders 2 and 3.
Clearly D1 = {Ki}. In fact, K1 is the only graph with dissociation number 1. Consider now the class D2. Since the only maximal dissociation set of order 1 in a graph is an isolated vertex, we see that a graph has dissociation number 2 if and only if it belongs to the class D2. It is also clear that complete graphs Kn, for n > 2, are in the class, because any pair of (adjacent) vertices forms a maximal dissociation set. Furthermore, if a matching M is removed from Kn, then every set consisting of a vertex is extended to a maximal dissociation set, consisting either of two adjacent or two non-adjacent vertices. We claim that these graphs are precisely all the graphs from D2. Suppose that G is not in the class of graphs obtained from complete graphs Kn with n > 2, by removing a (possibly empty) matching M from G. In this case G contains a vertex, say x, which is not adjacent to two vertices from G, say y and z. It is clear that {x, y, z} is a (not necessarily maximal) dissociation set, and hence G is not in D2. We have proved the following statement.
Observation 2.1. D2 = {Kn — M | n > 2, M a (possibly empty) matching in Kn}.
Note that the path P3 is one of the graphs from D2. In particular, as we will see in Theorem 3.2, this graph can be used in constructing infinite families of uniformly dissociated trees.
Next, we present two characterizations of the graphs in D3. The following lemma will be used in several proofs in the paper.
Lemma 2.2. Let G be a nontrivial uniformly dissociated graph and M an induced matching in G. If 2|M| < k and G € Dk, then G — N[V(M)] € Dk-2|M|.
296
Ars Math. Contemp. 13 (2017) 293-306
Proof. Assume that G G . Let M be an induced matching in G and assume that 21M | < k. Let Si and S2 be any maximal dissociation sets of G - N[V(M)]. It is clear that V(M) U S1 and V(M) U S2 are maximal dissociation sets of G, and consequently 2|M| +
|Si| = k = 2|M| + S2. This implies that |Si| = |S21, and therefore G - N[V(M)] G
2|M|.	□
Theorem 2.3. A graph G with at least one edge is in D3 if and only if
(1)	for every xy G E(G) we have |V(G) \ N[{x, y}]| = 1; and
(2)	for every uv G E(G) we have |V(G) \ N[{u, v}]| < 1, and if {u, v} is a maximal independent set of G, then N(u) = N(v).
Proof. Suppose that G is a uniformly dissociated graph with diss (G) = 3. That means that regardless of how we build a maximal dissociation set we end up with 3 vertices in it. Let xy G E(G). By Lemma 2.2, G - N[{x, y}] G D1, which implies property (1), because D1 contains only K1. Suppose u and v are two non-adjacent vertices. If |V(G) \ N[{u, v}] | > 1, then there exists a dissociation set, consisting of u, v, and two vertices from V(G) \ N[{u, v}], a contradiction with diss(G) = 3. This proves that |V(G) \ N[{u, v}]| < 1. Now, assume that {u, v} is a maximal independent set of G. If N(u) = N(v), then {u, v} is a maximal dissociation set, a contradiction, which completes the proof of one direction.
For the converse, assume that G satisfies properties (1) and (2). Consider any maximal dissociation set S of G. If S contains two adjacent vertices, then property (1) shows that S contains exactly three elements. Otherwise, S consists of an independent set of vertices, which is by (1) of size at least 2 (we can use (1), since G has an edge). Let u and v belong to S, C be the set of common neighbors of u and v, A = N(u) \ N(v), and B = N(v) \ N(u).
By (2), |V(G) \ N[{u, v}]| < 1; so first consider the case that G - N[{u, v}] = {w}. Note that (1) ensures that each vertex, say x, in A must be adjacent to every vertex in B, since if not, G - N[{u, x}] is not isomorphic to K1. Also observe that w must be adjacent to all vertices of A (resp. B). Suppose that w is not adjacent to u', where u' g A. Then G - N[{u, u'}] contains v and w, which contradicts (1) (we derive a similar contradiction, if v' g B is not adjacent to w). Now, note that since u and v belong to the independent set S no vertex in A U B U C does. Because S is maximal, we infer that S = {u, v, w}. Finally, consider the case when |V(G) \ N[{u,v}]| = 0. This means that {u, v} is a maximal independent set, and using property (2) we see that {u, v} is not a maximal dissociation set and |S| = 3.	□
Now, we present another characterization of the graphs from D3. If a graph G belongs to D3, then in its complement, which we denote by H, every pair of vertices that are non-adjacent have exactly one common neighbor (using condition (1) of Theorem 2.3 expressed in the complement of G). Condition (2) of the theorem expressed in H is that for every pair u and v of vertices that are adjacent in H there is at most one common neighbor of u and v. In other words, any edge of H belongs to at most one triangle. Hence H is diamondfree, and the second part of condition (2) implies that either u or v must have some other neighbor, which readily implies that H must be connected.
The described conditions for the graph H are equivalent to the definition of the so-called geodetic graphs with diameter 2 that are diamond-free. (Recall that a graph is geodetic, if between any pair of vertices there is a unique shortest path.) Since in geodetic graphs any cycle on 4 vertices lies in the complete graph on the same 4 vertices, we derive the following characterization of graphs from D3.
B. Bresar et al.: Uniformly dissociated graphs
297
Theorem 2.4. A graph G is in D3 if and only if its complement G is a connected K4-free geodetic graph with diameter 2.
Geodetic graphs with diameter 2 were studied by Stemple [16], (see also the monograph [6], where these graphs were further classified) who proved in [16, Result II] that triangle-free geodetic graphs with diameter 2 are precisely the Moore graphs with diameter 2 (and girth 5). There are three known graphs of this type - C5, the Petersen graph and the Hoffman-Singleton graph, which is a 7-regular graph on 50 vertices. It is one of the big open problems, whether there exist other Moore graphs. As the analysis shows, the only possible candidates for other Moore graphs are regular with degree 57 on 3250 vertices. If there exists such a Moore graph, it might not be unique. Note that the complement of any such graph (if it exists) is in D3.
The complement of a graph from D3 cannot have any 4-cycle as a subgraph, because the existence of an induced C4 or a diamond contradicts the characteristic property of geodetic graphs, and K4 is also forbidden. Now, if one forbids 4-cycles as subgraphs in a graph of diameter 2, then any two vertices that are not adjacent have exactly one common neighbor. Therefore, these are exactly the geodetic graphs with diameter 2, that is, the complements of graphs from D3. Bondy, Erdos, and Fajtlowicz characterized in [3] the graphs with diameter 2 that have no 4-cycles as the graphs H that fall into three different families:
(i)	A(H) = |V(H)| - 1 and H has no 4-cycles,
(ii)	H is a Moore graph,
(iii)	H is a polarity graph.
The first family are the graphs having a universal vertex, and all other vertices have degree at most 2. Clearly, the complement of any such graph is the disjoint union of a graph from D2 and Ki. While Moore graphs are well-known, let us focus on the third family - polarity graphs. The study of these graphs started in the context of projective geometries by Kantor [11], and they were later considered in several papers. See the recent study [1]. For a formal definition of polarity graphs we present some notions from finite geometries.
Let P and L be disjoint, finite sets, and let IcPx£. The triple (P, L, I) is called a finite geometry, elements of P are called points, while elements of L are lines. A polarity of the geometry is a bijection from P U L to PuL that sends points to lines, sends lines to points, is an involution, and respects the incidence structure. Given a finite geometry (P, L, I) and a polarity n, the polarity graph Gn is the graph with vertex set V(Gn) = P, andpq G E(Gn) whenever p and q are points such that (p, n(q)) G I.
Alternatively, for any prime power q, let PG(2, q) denote the standard projective geometry over the Galois field GF(q), where points are represented by projective triples, see [1] for details. The vertex set of the corresponding polarity graph consists of (q2 + q + 1) points of PG(2, q), which are adjacent whenever the corresponding triples are orthogonal. In particular, for any prime power q there exists a (unique) polarity graph, which readily implies that there are also infinitely many graphs in D3. From the result of Bondy, Erdos, and Fajtlowicz [3] and our discussion we derive another characterization of these graphs.
Corollary 2.5. A graph G is in D3 if and only if either G is the disjoint union of a graph from D2 and the D1-graph, or G is the complement of a Moore graph, or G is the complement of a polarity graph.
298
Ars Math. Contemp. 13 (2017) 293-306
In order to present some small examples of connected graphs in D3 we performed a structural analysis of these graphs, which results in the following proposition, the proof of which is omitted.
Proposition 2.6. Let G be a connected graph in D3 having minimum degree k.
(1)	If k < 2, then G = C5.
(2)	If k > 3 and v is a vertex in G such that deg(v) = k, then the open neighborhood of v partitions into £ subsets S1,... ,Se such that IS | = m for all i, k = £m, and m+1 < I < m + 2. In addition, B = V (G) \ N [v] = [bu ..., b£}, N (bi) n Si = 0 and bi is adjacent to every vertex in Sj for j = i. The subgraphs G[B], G[Si],..., G[S^] all belong to V2.
In the case that G[B] is a complete graph we are able to deduce that each G[Si] is also a complete graph. Indeed, let S(G[B]) = £ — 1, let 1 < i < £ and let s be any vertex in Si. For i = j, |V(G) \ N[{s, bj}]| = 1 and hence s is adjacent to exactly m — 1 vertices in Sj. If e denotes the number of neighbors of s in G[Si], then
m£ = k < deg(s) = 1 + e + (£ — 1) + (£ — 1)(m — 1).
From this it follows that e = m — 1, and we see that G[Si] is a complete subgraph.
When k > 3, £ > m, and k = £m, it follows that £ > 3. Next we find all graphs in D3 with £ = 3. Note that in this case m is either 1 or 2. Let A = N(v) where v is a vertex of minimum degree as in the statement of Proposition 2.6(2).
v
Figure 1: The only graph in D3 with i = 3 and m =1.
Suppose first that m = 1. In this case k = i and the subgraph G[A] is isomorphic to the complement of G[B]. Since G[B] G it follows that the maximum degree of G[A] is at most 1. If A is an independent set, then we get that G is isomorphic to the graph in Figure 1. On the other hand, if A(G[A]) = 1, then G is isomorphic to the graph in Figure 2, which is, in turn, isomorphic to the graph in Figure 1.
Next suppose that m = 2, and hence i = m + 1 = 3. As above, G[B] = K3 and G[Sj] = K2 for 1 < i < 3. As it turns out, the only possibility that yields a graph from V3 is that the subgraph G[A] is isomorphic to K2DK3; we derive that G is the graph in Figure 3. (Note that it is the complement of the Petersen graph.)
Stemple proved [16, Result X] that the order of a geodetic graph H with diameter 2, which has triangles but no complete subgraphs of order 4, is A2 - A + 1, where A is maximum degree of H. Note that A is equal to the maximum number of non-neighbors of vertices in G from D3, which is, by the construction from Proposition 2.6, equal to i. Hence i(m + 1) = A(A - 1). We deduce that unless the complement of G is triangle-free (and thus a Moore graph), we have i = m + 2. For i = m + 2 = 3 this is exactly
B. Bresar et al.: Uniformly dissociated graphs	299
v
Figure 2: A graph isomorphic to the one in Figure 1.
the graph in Figure 1. When i = m + 2 = 4 we have the graph in Figure 4. As in the description of the connected graphs in D3 from above, the vertex v is adjacent to all vertices in S = S1 U S2 U S3 U S4. For 1 < i < 4, bi is adjacent to every vertex in S — Si. The subgraph induced by B is a complete graph of order 4 with the matching edges blb2 and b3b4 removed. This graph, G[B], is in D2.
o v
B
Figure 4: Graph in D3 of order 13.
Let us only mention that the path P6 and the cycle C7 belong to D4, while a special family of graphs in V2k, where k > 3, will be presented in the next section.
3 Extendable vertices
The term extendable vertices of graphs was coined in the context of well-covered graphs, where such vertices were used as attachment vertices to build bigger graphs from smaller well-covered building blocks [7]. We will use a similar approach, and introduce extendable
300
Ars Math. Contemp. 13 (2017) 293-306
vertices in the context of uniformly dissociated graphs.
Let G be a uniformly dissociated graph with diss (G) = k. We say that x G V(G) is Vk-extendable, if the following two properties hold:
(i)	(G - x) g D and
(ii)	(G - N[x]) G Dk-1.
Since in this paper we use only this version of extendability, we will often simplify the wording by calling -extendable vertices just extendable vertices. It is clear that the only vertex of K1 (which is the only graph of D1) is not extendable in the above sense. On the other hand, it is easy to verify that all graphs from D2, except the complete graphs, contain an extendable vertex.
Proposition 3.1. Let G be any graph in D2, and G not a complete graph. Any vertex that is not universal in G, is V2-extendable.
The application of this concept in constructing large families of uniformly dissociated graphs is presented in the next result.
Theorem 3.2. Let G be an arbitrary graph, having vertices denoted by x1;..., xn; let G1;..., Gn be (not necessarily different) uniformly dissociated graphs, each having an extendable vertex. If G* is obtained from G by identifying x4 with an extendable vertex of Gj for all i G {1,..., n}, then G* is a uniformly dissociated graph.
The proof of the theorem follows directly from the construction of G* and the definition of extendable vertices. In particular, Theorem 3.2 shows that every graph is an induced subgraph of a uniformly dissociated graph. (Since non-complete graphs in D2 form an infinite family, every graph is an induced subgraph of infinitely many uniformly dissociated graphs.)
In the rest of this section, we shed some more light on the uniformly dissociated graphs, (not) having extendable vertices.
Proposition 3.3. No vertex of a connected graph from D3 is extendable.
Proof. Let G be a connected graph in D3, and assume that w g V(G) is an extendable vertex of G. If there exists an edge xy G E(G) such that w is adjacent to neither x nor to y, then by property (1) from Theorem 2.3, we infer that {x, y} is a maximal dissociation set of G - w, a contradiction with G - w gD3. Hence G - N[w] does not contain any edge, which implies that degG (w) > | V(G) | - 3 (for otherwise V(G) \ N(w) would be an independent set of cardinality at least 4). Now, if V(G) \ N [w] consisted of only one vertex, say y, then w and a neighbor of y would form a maximal dissociation set of G of size 2, again a contradiction. This implies that there exist exactly two vertices in the complement of N [w], and let us denote them by y and z.
If y and z had a common neighbor x, then again we derive a contradiction with G gD3 (because {w, x} would be a maximal dissociation set of G). This implies that N(y) n N(z) = 0, and each of N(y) and N(z) is non-empty, since G is connected. If there exists a vertex a G N(w) such that {y, z} n N(a) = 0, then {y, z} C V(G) \ N[{w, a}], which contradicts property (1) of Theorem 2.3. Thus N(y), N(z) is a partition of N(w). Now, if there exists y' G N(y) and z' G N(z) such that y'z' G E(G), then {y, y', z, z'} is a dissociation set of G of cardinality 4, a contradiction. Otherwise, the set {y', z'}, where y' G N(y) and z' G N(z), is a maximal dissociation set of G of cardinality 2, which is the final contradiction, showing that w is not an extendable vertex of G.	□
B. Bresar et al.: Uniformly dissociated graphs
301
There are many Dk-extendable vertices, where k is an even number; in fact, any vertex in the construction of a graph G* from Theorem 3.2, which corresponds to a vertex from the initial graph G, is extendable. On the other hand, we know of no example of a connected Dk-extendable vertex for k being odd. More precisely, we know that there are no D3-extendable vertices in connected graphs, and, in addition, we do not know if any connected V2£+i-extendable graphs exist, when I > 1. Therefore we pose the following question.
Question 3.4. Are there any connected graphs in Dk, where k is an odd number greater than 3? If there are, does there exist a Dk -extendable vertex for some such k.
It would be interesting to know, if any connected graphs in D2t+i, for t > 1 exist, also because they would present a natural common extension of the classes of Moore graphs with diameter 2 and polarity graphs.
4	Uniformly dissociated graphs with girth at least 7
Suppose that each of the graphs G1,..., Gn is isomorphic to P3. The construction given in Theorem 3.2 presents a large family of uniformly dissociated graphs, each of which has many leaves (in fact, a third of the vertices have degree 1). Note that in these graphs each neighbor of a leaf has degree 2, and is in particular adjacent to only one leaf. This latter property holds in all uniformly dissociated graphs that have minimum degree 1 and order at least 4, as the following lemma shows.
Lemma 4.1. Let G be a connected uniformly dissociated graph on more than three vertices. If x is a stem, then it has exactly one leaf as a neighbor.
Proof. Let G be a connected uniformly dissociated graph with |V(G)| > 3. For the purposes of reaching a contradiction, let us assume that there exists a vertex x, which is adjacent to more than one leaf. Let x1,..., xk, where k > 2, be the leaves adjacent to x. If G is the star K1k, then {x, x1} is a maximal dissociation set of size 2, and {x1,..., xk } a maximal dissociation set of size k, where k > 3, because G has at least 4 vertices. Hence G is not uniformly dissociated.
If G is not a star, then there exists a neighbor y of x, which is not a leaf. Let S be a maximal dissociation set that contains vertices x and y (such a set always exists, because we can start a greedy procedure of obtaining a dissociation set by picking the endvertices of the edge xy). Note that the leaves x1,..., xk are not in S, and, moreover, x and y are the only vertices from N[{x, y}] that are in S. Let S' = S \ {x, y}. Clearly, S' is a (maximal) dissociation set of G - N [{x, y}]. Now, let S be the set S ' U {y, x1,..., xk}. Note that
5	is a dissociation set of G (not necessarily maximal), and |S| > |S'| + 3 > |S|. Since S lies in a maximal dissociation set, we derive that G is not a uniformly dissociated graph, a contradiction, which shows that G contains no vertex adjacent to more than one leaf. □
Lemma 4.2. If G is a uniformly dissociated graph of order at least 3, then no two stems of G are adjacent.
Proof. Let G G Dm for some m > 2. If |V(G)| = 3, then G does not have two stems, so we may assume that G is of order greater than 3. Now, if m = 2, then G is isomorphic to a complete graph from which a (possibly empty) matching is removed (by Observation 2.1). Hence G has no leaves, and consequently also no stems. We may thus assume that G is a graph of order greater than 3, and G G Dm, for m > 3.
302
Ars Math. Contemp. 13 (2017) 293-306
Assume that G has two stems u and v that are adjacent. Let us denote by x and y the leaves that are adjacent to u and v, respectively. By Lemma 4.1 each stem is adjacent to exactly one leaf. Let Di be a maximal dissociation set that contains vertices u and v. By Lemma 2.2, as u and v form a vertex set of a trivial induced matching in G, we have G - N[{u, v}] € Dm-2. Now, note that D2 = Di U {x, y} \ {v} is a dissociation set of G, which is not necessarily maximal. Hence, there exists a maximal dissociation set in G that contains D2 and is of cardinality at least m + 1, a contradiction with G € Dm. □
In the rest of this section we restrict ourselves to graphs with girth at least 7.
Lemma 4.3. If G is a uniformly dissociated graph with g(G) > 7, then no two stems of G are at distance 2.
Proof. Let G be a uniformly dissociated graph, that is G € Dm for some m > 2, and let g(G) > 7. Assume that G has two stems v and w that are at distance 2, and let u be their common neighbor. Let us denote by x and y the leaves that are adjacent to v and w, respectively (by Lemma 4.1 each stem has only one leaf).
Denote by zi,..., zp the neighbors of w, different from u, and note that they are not stems and not leaves, by Lemma 4.2. Hence each of them has a neighbor, and let us denote them by Xr i i, .. ., Xr i j i,..., Xr p i . .. , Xr p j , where Xj , j are the neighbors of zj for all i € {1,... ,p}. Since xj , j are not leaves, each of them has another neighbor, and let us denote the neighbors of Xj,j by yj ,j,i,..., yj ,j,ki j for all i € {1,... ,p}, j € {1,..., jj}. Now, we build an induced matching M, consisted of edges Xj ,j yj ,j, k in the following way. As long as this is possible, for each zj choose a j from {1,..., j }, and add an edge Xj, jyj , j , k to M, so that it does not destroy the property of M being an induced matching. Note that since the girth is at least 7, the only possibility for destroying the property of M being an induced matching is that some vertex yjjjik is adjacent to a vertex yj',j',k', which is already in V(M). More precisely, the procedure can end before an edge Xj jyjjj k has been added to M for all zj, only if for some zj and for all of its neighbors Xj j all of their neighbors yjjjik cannot be chosen, because each of them is adjacent to some yj',j',k' that is an endvertex of an edge from M. In this case, by using Lemma 2.2, we infer that since M is an induced matching in G, and 2|M| < m, we have G - N[V(M)] € Dm-2|M|. Now, this implies that all neighbors of Xji,..., Xj (except for zj) are in N [V (M)] and thus in G — N[V(M)] all xj,i,..., xj,ji are leaves. Hence zj is a stem in G — N[V(M)] and is adjacent to w, which is also a stem in G — N[V(M)]. Now, this is a contradiction with Lemma 4.2, because G — N[V(M)] is a uniformly dissociated graph with two adjacent stems.
Hence, the only possibility is that the procedure of building an induced matching M consisted from edges xj,jyj,j,k ends, so that for each zj we have chosen one edge xj,jyj,j,k to belong to M. Since M is an induced matching and 2|M| < m, we have G—N[V(M)] € Dm-2|M | by Lemma 2.2. Note that in G—N [V (M)], w is a stem of degree 2 (adjacent only to u and the leaf y), and v also belongs to G—N[V(M)] because an edge between v and any yj,j,k in G would imply the existence of a 6-cycle. Now, let Di be a maximal dissociation set of G — N[V(M)], which contains v, u and y, and let D2 = Di U {x,w} \ {u}. Clearly, D2 is a dissociation set (not necessarily maximal) of cardinality |Di| + 1, which is a contradiction with G — N[V(M)] being uniformly dissociated. The proof is complete. □
Lemma 4.4. If G is a uniformly dissociated graph with g(G) > 7, then for each stem v,
deg(v) = 2.
B. Bresar et al.: Uniformly dissociated graphs
303
Proof. Let G G Dm for some m > 2, and assume that v is a stem adjacent to the leaf
x,	and v has at least two other neighbors, which we denote by w and w'. Now, we use a similar idea as in the proof of Lemma 4.3.
Denote by z^ ..., zp the neighbors of w, different from v, which are not stems and not leaves, by Lemma 4.2. Hence each of them has a neighbor, and let us denote them by
where Xi, j are the neighbors of zj for all i G {1,..., p}, j G {1,...,^}. Since Xjj are not leaves, each of them has another neighbor, and let us denote the neighbors of Xj,j by yj j,i,...	for all i G {1,... ,p}, j G {1,..., jj}. Now, we build an induced matching M, consisted of edges xj,j yj ,j, k in the following way. As long as this is possible, for each zj choose a j from {1,..., ji}, and add an edge
xi,jyi,j,fe	to M, so that it does not destroy the property of M being an induced matching. Note that since girth is 7, the only possibility for destroying the property of M being an induced matching is that some vertex yj,j,k is adjacent to a vertex yi',j',fe', which is already in M. More precisely, the procedure can end before an edge xj,jyj,j,fc has been added to M for all zj, only if for some zj and for all of its neighbors xj,j all of their neighbors yj,j,k cannot be chosen, because each of them is adjacent to some yj',j ,fe' that is an endvertex of an edge from M. In this case, by using Lemma 2.2, we infer that since M is an induced matching in G, and 2|M| < m, we have G-N[V(M)] G Dm-2|M|. Now, this implies that all neighbors of xj i,..., xj,ji (except for zj) are in N[V(M)] and thus in G - N[V(M)] all
Xj,i,..., Xj,ji are leaves. Hence zj is a stem in G - N[V(M)], which is at distance 2 from another stem v, a contradiction with Lemma 4.3.
Hence, the only possibility is that the procedure of building an induced matching M consisted from edges xj,jyj,j,fc ends, so that for each zj we have chosen one edge xj,jyj,j,fc to belong to M. Since M is an induced matching and 2|M| < m, we have G-N[V(M)] G Dm-2|M| by Lemma 2.2. Note that in G - N[V(M)], w is a leaf, adjacent only to v. Thus v is a stem, which is adjacent to two leaves, a contradiction with Lemma 4.1.	□
Lemma 4.5. If G is a uniformly dissociated graph with g(G) > 7 and has a leaf, then each vertex of G is either a leaf, or a stem or is adjacent to a stem.
Proof. Let G G Dm for some m > 2 with g(G) > 7 and with a leaf. We may assume that G is a connected graph. Suppose that there exists a vertex in G that is not a leaf, not a stem, and not adjacent to a stem. Since G is connected, there exists such a vertex w, which is, in addition, adjacent to u, which is in turn adjacent to a stem v.
Denote by zi,..., zp the neighbors of w, different from u, which are not leaves and not stems by our assumption. Hence each of them has a neighbor, and let us denote them by xi,i,..., xi,j1,..., xPji ..., xp,j , where
x j j are the neighbors of zj for all i G {1,... ,p}, j G {1,..., j^}. Since xj,j are not leaves (because zj are not stems), each of them has another neighbor, and let us denote the neighbors of xj,j by yj,j,i,..., yj,j,fci,j for all i G {1,... ,p}, j G {1,..., j^}. Now, we build an induced matching M, consisted of edges xj,jyj,j,fc in the following way. As long as this is possible, for each zj choose a j from {1,..., j^}, and add an edge xj,jyj,j,k to M, so that it does not destroy the property of M being an induced matching. Suppose that the procedure of building an induced matching M consisted from edges xj,jyj,j,fc ends, so that for each zj we have chosen one edge xj,jyj,j,k to belong to M. Since M is an induced matching and 2|M| < m, we have G - N[V(M)] G Dm-2|M| by Lemma 2.2. Note that in G - N[V(M)], w is a leaf, adjacent to u; thus u and v are two adjacent stems, a contradiction with Lemma 4.2. Thus the procedure of building an induced matching M such that all zj would be in N [V (M)]
304
Ars Math. Contemp. 13 (2017) 293-306
ends before each z has a neighbor xj,j added to V(M). Let z^ be such a vertex that for all neighbors xj/,j/ all of their neighbors % cannot be chosen, because each of them is adjacent to some yiijjfc that is an endvertex of an edge from M.
Suppose deg(zj/) > 2. Note that for all neighbors xj/,j/ all of their neighbors yj/,j/,fc/ are adjacent to a vertex yiijjfc g V(M). Since M an induced matching in G, and 2|M| < m, we have G - N[V(M)] g Dm_2|M|. This implies that all neighbors of x»/,i,..., xi/jj./ (except for z»/) are in N[V(M)] and thus in G — N[V(M)] all xj/,i,... , xj/ j./ are leaves. Hence z»/ is a stem in G — N[V(M)], which has at least two leaves, a contradiction with Lemma 4.1.
We may thus assume that deg(zj/) = 2, and let x»/ be the neighbor of z»/, different from w. Suppose that deg(x»/) > 2. By selecting the matching M', consisting only of the edge uv, we infer by Lemma 2.2 that G — N[V(M')] g Dm-2. Yet z»/ is a leaf in G — N[V(M')], and so x»/ is a stem, whose degree is more than 2, a contradiction with Lemma 4.4. Hence, we infer that also deg(xj/) = 2, and let y»/ be another neighbor of x»/. By the property of M, established above, we know that y»/ is adjacent to some yj, which is at distance 3 from w. Now, let M" be the matching consisting only of the edge y»/ y^-fc. Hence, G — N [V (M")] g Dm-2, but in G — N [V (M")] the vertex z»/ is a leaf, and so w is a stem. We derive that w and v are two stems in the uniformly dissociated graph G — N[V(M")], which are at distance 2, contradicting Lemma 4.3.	□
We join the previous lemmas into the following fact.
Observation 4.6. If G is a uniformly dissociated graph with g(G) > 7 and has a leaf, then every vertex that is not a stem nor a leaf, is adjacent to exactly one stem. Note that in that case G has the structure as presented in the construction from Theorem 3.2, where each of the extendable graphs, identified with a vertex from an arbitrary graph, is isomorphic to P3.
The above observation is correct, because if a vertex were adjacent to two stems, these two stems would be at distance 2, which is a contradiction with Lemma 4.3.
Lemma 4.7. If G is a connected uniformly dissociated graph with g(G) > 7 and ¿(G) > 2, then G is isomorphic to C7.
Proof. Let G g Dm for some m > 2, g(G) > 7, and ¿(G) > 2. Assume that there exists a vertex v, with deg(v) > 3.
Suppose that there exists a neighbor w of v, with deg(w) = 2. Let z be the neighbor of w, different from v; further let x be a neighbor of z, and y a neighbor of x, different from z. Note that y is not adjacent to v nor to any of its neighbors, due to the girth restriction. Let M be the matching consisting only of the edge xy. Hence, G — N[V(M)] g Dm-2, but in G — N[V(M)] the vertex w is a leaf, and so v is a stem. Since degG-N[V(M) (v) > 3 we are in contradiction with Lemma 4.4.
The remaining possibility is that all neighbors of v have degree at least 3. Since G is connected, we derive that every vertex in G has degree at least 3. We conclude the proof by using the base technique from the proofs of previous lemmas.
Let v g V(G), w one of its neighbors, and denote by z1,..., zp the neighbors of w, different from v. Each of them has a neighbor, which we denote by
xi, 1,..., xi,ji,..., xp, 1 ..., xp,jp,
B. Bresar et al.: Uniformly dissociated graphs
305
where are the neighbors of zi for all i e {1,... ,p},j € {1,... ,ji}. Each of xi,j has another neighbor, and let us denote the neighbors of xijj by yi,j,i,..., yi,j,ki:j for all i € {1,... ,p}, j € {1,..., ji}. Now, we build an induced matching M, consisted of edges xi,jyiijik in the following way. As long as this is possible, for each zi choose a j from {1,..., ji}, and add an edge xijjyiijik to M, so that it does not destroy the property of M being an induced matching. Note that since girth is 7, the only possibility for destroying the property of M being an induced matching is that some vertex yi j k is adjacent to a vertex yi> j/ k/, which is already in M. More precisely, the procedure can end before an edge xi,j yijjjk has been added to M for all zi, only if for some zi and for all of its neighbors xi j all of their neighbors yijjjk cannot be chosen, because each of them is adjacent to some yi',j',k' that is an endvertex of an edge from M. In this case, by using Lemma 2.2, we infer that since M an induced matching in G, and 2|M| < m, we have G — N[V(M)] e Dm_2|M|. Now, this implies that all neighbors of xi1,... ,xi j. (except for zi) are in N[V(M)] and thus in G — N[V(M)] all x^i,... , xi ji are leaves. Hence zi is a stem in G — N[V(M)], which has degree at least 3, a contradiction with Lemma 4.4.
Hence, the only possibility is that the procedure of building an induced matching M consisted from edges xi,jyijjjk ends, so that for each zi we have chosen one edge xi,jyijjjk to belong to M. Since M is an induced matching and 2|M| < m, we have G —N[V(M)] e Dm_2|M| by Lemma 2.2. Note that in G — N[V(M)], w is a leaf, adjacent only to v. Thus v is a stem with degree at least 3, again the contradiction with Lemma 4.4.
As a result of this we now conclude that G is a connected, uniformly dissociated, regular graph of degree 2 and girth at least 7. It is straightforward to check that C7 is the only cycle of order seven or more that is uniformly dissociated.	□
We are ready to state the main theorem.
Theorem 4.8. If G is a uniformly dissociated graph with g(G) > 7, then each connected component of G is either isomorphic to C7, or can be obtained from an arbitrary connected graph H with girth at least 7, by identifying each vertex of H with a leaf of a copy of P3.
References
[1]	M. Bachraty and J. Siran, Polarity graphs revisited, Ars Math. Contemp. 8 (2015), 55-67, http://amc-journal.eu/index.php/amc/article/view/52 7.
[2]	R. Boliac, K. Cameron and V. V. Lozin, On computing the dissociation number and the induced matching number of bipartite graphs, Ars Combin. 72 (2004), 241-253, http: //www.combinatorialmath.ca/arscombinatoria/vol72.html.
[3]	J. A. Bondy, P. Erd6s and S. Fajtlowicz, Graphs of diameter two with no 4-circuits, Discrete Math. 200 (1999), 21-25, doi:10.1016/s0012-365x(98)00321-5.
[4]	B. Bresar, M. Jakovac, J. Katrenic, G. Semanisin and A. Taranenko, On the vertex fc-path cover, Discrete Appl. Math 161 (2013), 1943-1949, doi:10.1016/j.dam.2013.02.024.
[5]	B. Bresar, F. Kardos, J. Katrenic and G. Semanisin, Minimum fc-path vertex cover, Discrete Appl. Math. 159 (2011), 1189-1195, doi:10.1016/j.dam.2011.04.008.
[6]	A. E. Brouwer, A. M. Cohen and A. Neumaier, Distance-Regular Graphs, volume 18 of Ergebnisse der Mathematik und ihrer Grenzgebiete, Springer-Verlag, Berlin, 1989, doi: 10.1007/978-3-642-74341-2.
[7]	A. Finbow, B. Hartnell and R. J. Nowakowski, A characterization of well covered graphs of girth 5 or greater, J. Combin. Theory Ser. B 57 (1993), 44-68, doi:10.1006/jctb.1993.1005.
306
Ars Math. Contemp. 13 (2017) 293-306
[8]	R. Gallant, G. Gunther, B. L. Hartnell and D. F. Rail, Limited packings in graphs, Discrete Appl. Math. 158 (2010), 1357-1364, doi:10.1016/j.dam.2009.04.014.
[9]	B. L. Hartnell and P. D. Vestergaard, Equipackable graphs, Bull. Inst. Combin. Appl. 46 (2006), 35-48, http://www.combinatorialmath.ca/ICA/ICA4 6.html.
[10]	M. Jakovac and A. Taranenko, On the k-path vertex cover of some graph products, Discrete Math. 313 (2013), 94-100, doi:10.1016/j.disc.2012.09.010.
[11]	W. M. Kantor, Moore geometries and rank 3 groups having p =1, Q. J. Math. 28 (1977), 309-328, doi:10.1093/qmath/28.3.309.
[12]	F. Kardos, J. Katrenic and I. Schiermeyer, On computing the minimum 3-path vertex cover and dissociation number of graphs, Theor. Comput. Sci. 412 (2011), 7009-7017, doi:10.1016/j.tcs. 2011.09.009.
[13]	Y. Orlovich, A. Dolgui, G. Finke, V. Gordon and F. Werner, The complexity of dissociation set problems in graphs, Discrete Appl. Math. 159 (2011), 1352-1366, doi:10.1016/j.dam.2011.04. 023.
[14]	C. H. Papadimitriou and M. Yannakakis, The complexity of restricted spanning tree problems, J. Assoc. Comput. Mach. 29 (1982), 285-309, doi:10.1145/322307.322309.
[15]	M. D. Plummer, Some covering concepts in graphs, J. Combin. Theory 8 (1970), 91-98, doi: 10.1016/s0021-9800(70)80011-4.
[16]	J. G. Stemple, Geodetic graphs of diameter two, J. Combin. Theory Ser. B 17 (1974), 266-280, doi:10.1016/0095-8956(74)90033-1.