Given a finite projective plane of order \(n\). A quadrangle consists of four points \(A, B, C, D\), no three collinear. If the diagonal points are non-collinear, the quadrangle is called a non-Fano quad. A general sum of squares theorem is proved for the distribution of points in a plane containing a non-Fano quad, whenever \(n \geq 7\). The theorem implies that the number of possible distributions of points in a plane of order \(n\) is bounded for all \(n \geq 7\). This is used to give a simple combinatorial proof of the uniqueness of \(PP(7)\).

Let \(G = (V, E)\) be a graph with \(n\) vertices. The clique graph of \(G\) is the intersection graph \(K(G)\) of the set of all (maximal) cliques of \(G\) and \(K\) is called the clique operator. The iterated clique graphs \(K^*(G)\) are recursively defined by \(K^0(G) = G\) and \(K^i(G) = K(K^{i-1}(G))\), \(i > 0\). A graph is \(K\)-divergent if the sequence \(|V(K^i(G))|\) of all vertex numbers of its iterated clique graphs is unbounded, otherwise it is \(K\)-convergent. The long-run behaviour of \(G\), when we repeatedly apply the clique operator, is called the \(K\)-behaviour of \(G\).

In this paper, we characterize the \(K\)-behaviour of the class of graphs called \(p\)-trees, that has been extensively studied by Babel. Among many other properties, a \(p\)-tree contains exactly \(n – 3\) induced \(4\)-cycles. In this way, we extend some previous results about the \(K\)-behaviour of cographs, i.e., graphs with no induced \(P_4\)s. This characterization leads to a polynomial-time algorithm for deciding the \(K\)-convergence or \(K\)-divergence of any graph in the class.

In this paper, we obtain a general enumerating functional equation about rooted pan-fan maps on nonorientable surfaces. Based on this equation, an explicit expression of rooted pan-fan maps on the Klein bottle is given. Meanwhile, some simple explicit expressions with up to two parameters: the valency of the root face and the size for rooted one-vertexed maps on surfaces (Klein bottle, Torus, \(N_3\)) are provided.

Let us denote by \({EX}(m,n; \{C_4,\ldots,C_{2t}\})\) the family of bipartite graphs \(G\) with \(m\) and \(n\) vertices in its classes that contain no cycles of length less than or equal to \(2t\) and have maximum size. In this paper, the following question is proposed: does always such an extremal graph \(G\) contain a \((2t + 2)\)-cycle? The answer is shown to be affirmative for \(t = 2,3\) or whenever \(m\) and \(n\) are large enough in comparison with \(t\). The latter asymptotical result needs two preliminary theorems. First, we prove that the diameter of an extremal bipartite graph is at most \(2t\), and afterwards we show that its girth is equal to \(2t + 2\) when the minimum degree is at least \(2\) and the maximum degree is at least \(t + 1\).

In Algebraic Graph Theory, Biggs \([2]\) gives a method for finding the chromatic polynomial of any connected graph by computing the Tutte polynomial. It is used by Biggs \([2]\) to compute the chromatic polynomial of Peterson’s graph. In \(1972\) Sands \([4]\) developed a computer algorithm using matrix operations on the incidence matrix to compute the Tutte Polynomial. In \([1]\), Anthony finds the worst-case time-complexity of computing the Tutte Polynomial. This paper shows a method using group-theoretical properties to compute the Tutte polynomial for Cayley graphs which improves the time-complexity.

Let \(N({Z})\) denote the set of all positive integers (integers). The sum graph \(G_S\) of a finite subset \(S \subset N({Z})\) is the graph \((S, E)\) with \(uv \in E\) if and only if \(u+v \in S\). A graph \(G\) is said to be an (integral) sum graph if it is isomorphic to the sum graph of some \(S \subset N({Z})\). The (integral) sum number \(\sigma(G)\) of \(G\) is the smallest number of isolated vertices which when added to \(G\) result in an (integral) sum graph. A mod (integral) sum graph is a sum graph with \(S \subset {Z}_m \setminus \{0\}\) (\(S \subset {Z}_m\)) and all arithmetic performed modulo \(m\) where \(m \geq |S|+1\) (\(m \geq |S|\)). The mod (integral) sum number \(\rho(G)\) of \(G\) is the least number \(\rho\) (\(\psi\)) of isolated vertices \(\rho K_1\) (\(\psi K_1\)) such that \(G \cup \rho K_1\) (\(G \cup \psi K_1\)) is a mod (integral) sum graph. In this paper, the mod (integral) sum numbers of \(K_{r,s}\) and \(K_n – E(K_r)\) are investigated and bounded, and \(n\)-spoked wheel \(W_n\) is shown to be a mod integral sum graph.

In this paper, the forcing domination numbers of the graphs \(P_n \times P_3\) and \(C_n \times P_3\) are completely determined. This improves the previous results on the forcing domination numbers of \(P_n \times P_2\) and \(C_n \times P_2\).

The stabilizers of the minimum-weight codewords of the binary codes obtained from the strongly regular graphs \(T(n)\) defined by the primitive rank-\(3\) action of the alternating groups \(A_n\), where \(n \geq 5\), on \(\Omega^{(2)}\), the set of duads of \(\Omega = \{1,2,\ldots,n\}\) are examined. For a codeword \(w\) of minimum-weight in the binary code \(C\) obtained as stated above, from an adjacency matrix of the triangular graph \(T(n)\) defined by the primitive rank-3 action of the alternating groups \(A_n\) where \(n \geq 5\), on \(\Omega^{(2)}\), the set of duads of \(\Omega = \{1,2,\ldots,n\}\), we determine the stabilizer \(Aut(C)_w\) in \(Aut(C)\) and show that \(Aut(C)_w\) is a maximal subgroup of \(Aut(C)\).

For a graph \(G\), let \(\mathcal{D}(G)\) be the set of strong orientations of \(G\). Define \(\overrightarrow{d}(G) = \min\{d(D) \mid D \in \mathcal{D}(G)\}\) and \(\rho(G) = \overrightarrow{d}(G) – d(G)\), where \(d(D)\) (resp. \(d(G)\)) denotes the diameter of the digraph \(D\) (resp. graph \(G\)). In this paper, we determine the exact value of \(\rho(K_r \times K_s)\) for \(r \leq s\) and \((r,s) \not\in \{(3,5), (3,6), (4,4)\}\), where \(K_r \times K_s\) denotes the tensor product of \(K_r\) and \(K_s\). Using the results obtained here, a known result on \(\rho(G)\), where \(G\) is a regular complete multipartite graph is deduced as corollary.