In this paper, we study the flexibility of embeddings of circular graphs \(C(2n,2)\), \(n \geq 3\) on the projective plane. The numbers of (non-equivalent) embeddings of \(C(2n, 2)\) on the projective plane are obtained, and by describing structures of these embeddings, the numbers of (non-equivalent) weak embeddings and strong embeddings of \(C(2n, 2)\) on the projective plane are also obtained.

In \([4]\), Elizalde and Pak gave a bijection \(\Theta: S_n(321) \to S_n(132)\) that commutes with the operation of taking inverses and preserves the numbers of fixed points and excedances for every \(\Gamma \in S_n(321)\). In \([1]\) it was shown that another bijection \(\Gamma: S_n(321) \to S_n(132)\) introduced by Robertson in \([7]\) has these same properties, and in \([2]\) a pictorial reformulation of \(\Gamma\) was given that made it clearer why \(\Gamma\) has these properties. Our purpose here is to give a similar pictorial reformulation of \(\Theta\), from which it follows that, although the original definitions of \(\Theta\) and \(\Gamma\) make them appear quite different, these two bijections are in fact related to each other in a very simple way, by using inversion, reversal, and complementation.

Gyarfas conjectured that for a given forest \(F\), there exists an integer function \(f(F,w(G))\) such that \(\chi(G) \leq f(F,w(G))\) for any \(F\)-free graph \(G\), where \(\chi(G)\) and \(w(G)\) are respectively, the chromatic number and the clique number of G. Let G be a \(C_5\)-free graph and \(k\) be a positive integer. We show that if \(G\) is \((kP_1, + P_2)\)-free for \(k \geq 2\), then \(\chi(G) \leq 2w^{k-1} \sqrt{w}\); if \(G\) is \((kP_1, + P_3)\)-free for \(k \geq 1\), then \(\chi(G) \leq w^k \sqrt{w}\). A graph \(G\) is \(k\)-divisible if for each induced subgraph \(H\) of \(G\) with at least one edge, there is a partition of the vertex set of \(H\) into \(k\) sets \({V_1,… , V_k}\) such that no \(V_i\); contains a clique of size \(w(G)\). We show that a \((2P_1+P_2)\)-free and \(C_5\)-free graph is \(2\)-divisible.

The concept of the sum graph and integral sum graph were introduced by F. Harary. Let \(\mathbb{N}\) denote the set of all positive integers. The sum graph \(G^+(S)\) of a finite subset \(S \subset {N}\) is the graph \((S, E)\) with \(uv \in E\) if and only if \(u+v \in S\). A simple graph \(G\) is said to be a sum graph if it is isomorphic to a sum graph of some \(S \subset {N}\). The sum number \(\sigma(G)\) of \(G\) is the smallest number of isolated vertices which when added to \(G\) result in a sum graph. Let \(\mathbb{Z}\) denote the set of all integers. The integral sum graph \(G^+(S)\) of a finite subset \(S \subset {Z}\) is the graph \((S, E)\) with \(uv \in E\) if and only if \(u+v \in S\). A simple graph \(G\) is said to be an integral sum graph if it is isomorphic to an integral sum graph of some \(S \subset {Z}\). The integral sum number \(\zeta(G)\) of \(G\) is the smallest number of isolated vertices which when added to \(G\) result in an integral sum graph. In this paper, we investigate and determine the sum number and the integral sum number of the graph \(K_n \setminus E(C_{n-1})\). The results are presented as follows:\(\zeta(K_n \setminus (C_{n-1})) = \begin{cases}
0, & n = 4,5,6,7 \\
2n-7, & n \geq 8
\end{cases}\)
and
\(\sigma(K_n \setminus E(C_{n-1})) = \begin{cases}
1, & n = 4 \\
2, & n = 5\\
5, & n = 5\\
7, & n = 7\\
2n-7, & n \geq 8
\end{cases}\)

The topic is the hat problem, in which each of \(n\) players is randomly fitted with a blue or red hat. Then, everybody can try to guess simultaneously their own hat color by looking at the hat colors of the other players. The team wins if at least one player guesses their hat color correctly, and no one guesses their hat color wrong; otherwise, the team loses. The aim is to maximize the probability of winning. In this version, every player can see everybody excluding themselves. We consider such a problem on a graph, where vertices correspond to players, and a player can see each player to whom they are connected by an edge. The solution of the hat problem on a graph is known for trees and for the cycle \(C_4\). We solve the problem on cycles with at least nine vertices.

Let \(D(G)\) be the Davenport constant of a finite abelian group \(G\), defined as the smallest positive integer \(d\) such that every
sequence of \(d\) elements in \(G\) contains a nonempty subsequence with sum zero the identity of \(G\). In this short note, we use group rings as a tool to characterize the Davenport constant.

It is proved that if \(G\) is a \(K_{2,3}\)-minor-free graph with maximum degree \(\Delta\), then \(\Delta+ 1 \leq \chi(G^2) \leq ch(G^2) \leq \Delta+2\) if \(\Delta \geq 3\), and \(ch(G^2) = \chi(G^2) = \Delta+1\) if \(\Delta \geq 6\). All inequalities here are sharp,even for outerplanar graphs.

Here, we determine all graphs of order less than \(7\) which are not product cordial.Also, we give some families of graphs which are product cordial.

A path in an edge-colored graph \(G\), where adjacent edges may be colored the same, is called a rainbow path if no two edges of the path are colored the same. For a \(k\)-connected graph \(G\) and an integer \(k\) with \(1 \leq k \leq \kappa\), the rainbow \(k\)-connectivity \(rc_k(G)\) of \(G\) is defined as the minimum integer \(j\) for which there exists a \(j\)-edge-coloring of \(G\) such that any two distinct vertices of \(G\) are connected by \(k\) internally disjoint rainbow paths. Denote by \(K_{r,r}\) an \(r\)-regular complete bipartite graph. Chartrand et al. in in “G. Chartrand, G.L. Johns, K.A.McKeon, P. Zhang, The rainbow connectivity of a graph, Networks \(54(2009), 75-81”\) left an open question of determining an integer \(g(k)\) for which the rainbow \(k\)-connectivity of \(K_{r,r}\) is \(3\) for every integer \(r \geq g(k)\). This short note is to solve this question by showing that \(rc_k(K_{r,r}) = 3\) for every integer \(r \geq 2k\lceil\frac{k}{2}\rceil\), where \(k \geq 2\) is a positive integer.

Let \(G\) be a connected graph with edge set \(E(G)\). The Balaban index of \(G\) is defined as \(J(G) = \frac{m}{\mu+1} \sum_{uv \in E(G)} ({D_uD_v})^{-\frac{1}{2}}\) where \(m = |E(G)|\), and \(\mu\) is the cyclomatic number of \(G\), \(D_u\) is the sum of distances between vertex \(u\) and all other vertices of \(G\). We determine \(n\)-vertex trees with the first several largest and smallest Balaban indices.