It is known that triangle-free graphs of diameter \(2\) are just maximal triangle-free graphs. Kantor ([5]) showed that if \(G\) is a triangle-free and \(4\)-cycle free graph of diameter \(2\), then \(G\) is either a star or a Moore graph of diameter \(2\); if \(G\) is a \(4\)-cycle free graph of diameter \(2\) with at least one triangle, then \(G\) is either a star-like graph or a polarity graph (defined from a finite projective plane with polarities) of order \(r^2 + r + 1\) for some positive integer \(r\) (or \(P_r\)-\({graph}\) for short). We study, by purely graph theoretical means, the structure of \(P_r\)-graphs and construct \(P_r\)-graphs for small values of \(r\). Further, we characterize graphs of diameter \(2\) without \(5\)-cycles and \(6\)-cycles, respectively. In general, one can characterize \(C_k\)-free graphs of diameter \(2\) with \(k > 6\) with a similar approach.

Dey’s formula can be used to count the subgroups of finitely generated groups and to establish congruence properties of subgroup counting functions. We develop an algebraic technique based on this formula for counting the subgroups of given index in Hecke groups, and show how to streamline it for efficient computation modulo \(2\).

A simple graph \(G\) with a perfect matching is said to be \({k-extendable}\) if for every set \(M\) of \(k\) independent edges, there exists a perfect matching in \(G\) containing all the edges of \(M\). In an earlier paper, we characterized \((n-2)\)-extendable graphs on \(2n \geq 10\) vertices. In this paper, we complete the characterization by resolving the remaining small cases of \(2n = 6\) and \(8\). In addition, the subclass of \(k\)-extendable graphs that are “critical” and “minimal” are determined.

Given a graph \(G = (V, E)\) and a vertex subset \(D \subseteq V\), a subset \(S \subseteq V\) is said to realize a “parity assignment” \(D\) if for each vertex \(v \in V\) with closed neighborhood \(N[v]\) we have that \(|N[v] \cap S|\) is odd if and only if \(v \in D\). Graph \(G\) is called all parity realizable if every parity assignment \(D\) is realizable. This paper presents some examples and provides a constructive characterization of all parity realizable trees.

The set of all possible intersection sizes between two simple triple systems \({TS}(v, \lambda_1)\) and \({TS}(v, \lambda_2)\) is denoted by \({Int}(v, \lambda_1, \lambda_2)\). In this paper, for \(6 \leq v \leq 14\), and for all feasible \(\lambda\)’s, \({Int}(v, \lambda_1, \lambda_2)\) is determined.

In this paper we obtain further results on the Multiplier Conjecture for the case \(n = 2n_1\), using our method.

A graph \(H\) is \(G\)-decomposable if \(H\) can be decomposed into subgraphs, each of which is isomorphic to \(G\). A graph \(G\) is a greatest common divisor of two graphs \(G_1\) and \(G_2\) if \(G\) is a graph of maximum size such that both \(G_1\) and \(G_2\) are \(G\)-decomposable. The greatest common divisor index of a graph \(G\) of size \(q \geq 1\) is the greatest positive integer \(n\) for which there exist graphs \(G_1\) and \(G_2\), both of size at least \(nq\), such that \(G\) is the unique greatest common divisor of \(G_1\) and \(G_2\). If no such integer \(n\) exists, the greatest common divisor index of \(G\) is infinite. Several graphs are shown to have infinite greatest common divisor index, including matchings, stars, small paths, and the cycle \(C_4\). It is shown for an edge-transitive graph \(F\) of order \(p\) with vertex independence number less than \(p/2\) that if \(G\) is an \(F\)-decomposable graph of sufficiently large size, then \(G\) is also \((F – e) \cup K_2 -\)decomposable. From this it follows that each such edge-transitive graph has finite index. In particular, all complete graphs of order at least \(3\) are shown to have greatest common divisor index \(1\) and the greatest common divisor index of the odd cycle \(C_{2k+1}\) lies between \(k\) and \(4k^2 – 2k – 1\). The graphs \(K_{p} – e\), \(p \geq 3\), have infinite or finite index depending on the value of \(p\); in particular, \(K_{p} – e\) has infinite index if \(p \leq 5\) and index \(1\) if \(p \geq 6\).

We prove that the set edge-reconstruction conjecture is true for graphs with at most two graphs in the set of edge-deleted subgraphs.

We determine all borders of the \(n\underline{th}\) Fibonacci string, \(f_n\), for \(n \geq 3\). In particular, we give two proofs that the longest border of \(f_n\) is \(f_{n-2}\). One proof is independent of the Defect Theorem.

Let \(G\) be a finite graph with vertices \(\xi_1, \ldots, \xi_n\), and let \(S_1, \ldots, S_n\) be disjoint non-empty finite sets. We give a new proof of a theorem characterizing the least possible number of connected components of a graph \(D\) such that \(V(D) = S_1 \cup \cdots \cup S_n\), \(E(D) = E(G)\) and, when an edge \(\lambda\) joins vertices \(\xi_i, \xi_j\) in \(G\), it is required to join some element of \(S_i\) to some element of \(S_j\) in \(D\) (so that, informally, \(D\) arises from \(G\) by splitting each vertex \(\xi_i\) into \(|S_i|\) vertices).