Let \(\mathbb{F}_q = \text{GF}(q^n)\) denote the finite field of order \(q^n\), and let \(U_n = \cup_{i=1}^{n}(\mathbb{F}_i,)\). Explicit permutation-type formulas for the Frobenius map \(\varphi\) (defined by \((\varphi(x)) = x^q\)) on \(\mathbb{F}_n\) and on \(U_n\) are obtained by using the well-known number \(N_q\) (the number of monic irreducible polynomials of degree \(i\) in \(\mathbb{F}_1[x]\)). Some results in [1] and [2] can be obtained from these formulas. Moreover, some other results are also given by using Pólya’s counting theory.

The composition of two graphs \(G\) and \(H\), written \(G[H]\), is the graph with vertex set \(V(G) \times V(H)\) and \((u_1,v_1)\) is adjacent to \((u_2,v_2)\) if \(u_1\) is adjacent to \(u_2\) in \(G\) or if \(u_1 = u_2\) and \(v_1\) is adjacent to \(v_2\) in \(H\). The \(r\)th power of graph \(G\), denoted \(G^r\), is the graph with vertex set \(V(G)\) and edge set \(\{(u,v) : d(u,v) \leq r \text{ in } G\}\). The bandwidth of graph \(G\) is \(\min \max |f(u) – f(v)|\), where the max is taken over each edge \(uv \in E(G)\), and the min is over all proper numberings \(f\). This paper establishes tight upper and lower bounds for the bandwidth of an arbitrary graph composition \(G[H]\), with the upper bound based only on \(|V(H)|\) and the bandwidth of \(G\). In addition, the exact bandwidth of the composition of \(G[H]\) is established for \(G\) the power of a path or a cycle.

The edge-neighbor-connectivity of a graph \(G\) is the minimum size of all edge-cut-strategies of \(G\), where an edge-cut-strategy consists of a set of common edges of double stars whose removal disconnects the graph \(G\) or leaves a single vertex or \(\emptyset\). This paper discusses the extreme values of the edge-neighbor-connectivity of graphs relative to the connectivity, \(\kappa\), and gives two classes of graphs — one class with minimum edge-neighbor-connectivity, and the other one with maximum edge-neighbor-connectivity.

In \([V_2]\), Vince outlined three potential graph algorithms for \(S^3\) recognition, namely shelling, reducing, and closing; on the other hand, he conjectured that the graph \(H_0\ ) of Fig.1 – which proves the first two to fail – could be a counterexample for the third one, too. This note shows that the conjecture is false; so, the validity of the closing algorithm is still an open problem.

We consider two variations of the classical Ramsey number. In particular, we seek the number of vertices necessary to force the existence of an induced regular subgraph on a prescribed number of vertices.

The \(i\)-center \(C_i(G)\) of a graph \(G\) is the set of vertices whose distances from any vertex of \(G\) are at most \(i\). A vertex set \(X\) \(k\)-dominates a vertex set \(Y\) if for every \(y \in Y\) there is a \(x \in X\) such that \(d(x,y) \leq k\). In this paper, we prove that if \(G\) is a \(P_t\)-free graph and \(i \geq \lfloor\frac{t}{2}\rfloor \), then \(C_i(G)\) \((q+1)\)-dominates \(C_{i+q}(G)\), as conjectured by Favaron and Fouquet [4].

As a generalization of a matching consisting of edges only, Alavi et al. in [1] define a total matching which may contain both edges and vertices. Using total matchings, [1] defines a parameter \(\beta’_2(G)\) and proves that \(\beta’_2(G) \leq p-1\) holds for a connected graph of order \(p \geq 2\).
Our main result is to improve this inequality to \(\beta’_2(G) \leq p-2\sqrt{p}+{2}\) and we give an example demonstrating this bound to be best possible.
Relations of several other parameters to \(\beta’_2\) are demonstrated.