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.

For a graph \(G = (V, E)\), \(X \subseteq V\) is a global dominating set if \(X\) dominates both \(G\) and the complement graph \(\bar{G}\). A set \(X \subseteq V\) is a packing if its pairwise members are distance at least \(3\) apart. The minimum number of vertices in any global dominating set is \(\gamma_g(G)\), and the maximum number in any packing is \(\rho(G)\). We establish relationships between these and other graphical invariants, and characterize graphs for which \(\rho(G) = \rho(\bar{G})\). Except for the two self-complementary graphs on \(5\) vertices and when \(G\) or \(\bar{G}\) has isolated vertices, we show \(\gamma_g(G) \leq \lfloor n/2 \rfloor\), where \(n = |V|\).

The inverse degree \(r(G)\) of a finite graph \(G = (V, E)\) is defined by \(r(G) = \sum_{v\in V} \frac{1}{deg(v)}\) where \(deg(v)\) is the degree of \(v\) in \(G\). Erdős \(et\) \(al\). proved that, if \(G\) is a connected graph of order \(n\), then the diameter of \(G\) is less than \((6r(G) + \sigma(1))\frac{\log n}{\log \log n}\). Dankelmann et al. improved this bound by a factor of approximately \(2\). We give the sharp upper bounds for trees and unicyclic graphs, which improves the above upper bounds.

Let \(\gamma_c(G)\) be the connected domination number of \(G\) and \(\gamma_{tr}(G)\) be the tree domination number of \(G\). In this paper, we study the generalized Petersen graphs \(P(n,k)\), prove \(\gamma_c(P(n, k)) = \gamma_{tr}(P(n, k))\) and show their exact values for \(k = 1, 2, \ldots, \lfloor n/2 \rfloor\).

Given a parity-check matrix \({H}\) with \(n\) columns, an \(\ell\)-subset \(T\) of \(\{1,2,\ldots,n\}\) is called a stopping set of size \(\ell\) for \({H}\) if the \(\ell\)-column submatrix of \({H}\) consisting of columns with coordinate indexes in \(T\) has no row of Hamming weight one. The size of the smallest non-empty stopping sets for \({H}\) is called the stopping distance of \({H}\).

In this paper, the stopping distance of \({H}_{m}(2t+1)\), parity-check matrices representing binary \(t\)-error-correcting \(BCH\) codes, is addressed. It is shown that if \(m\) is even then the stopping distance of this matrix is three. We conjecture that this property holds for all integers \(m \geq 3\).