Fouquet and Jolivet conjectured that if \(G\) is a \(k\)-connected \(n\)-vertex graph with independence number \(\alpha \geq k \geq 2\), then \(G\) has circumference at least \( \frac{k(n+\alpha-k)}{\alpha} \). This conjecture was recently proved by \(O\), West, and Wu.
In this note, we consider the set of \(k\)-connected \(n\)-vertex graphs with independence number \(\alpha > k \geq 2\) and circumference exactly \( \frac{k(n+\alpha-k)}{\alpha} \). We show that all of these graphs have a similar structure.

Let \(\Gamma\) be the rank three \(M_{24}\) maximal \(2\)-local geometry. For the two conjugacy types of involution in \(M_{24}\), we describe the fixed point sets of chambers in \(\Gamma\).

In this paper, all connected graphs with the fourth largest signless-Laplacian eigenvalue less than two are determined.

The Lights Out game on a graph \(G\) is played as follows. Begin with a (not necessarily proper) coloring of \(V(G)\) with elements of \(\mathbb{Z}_2\). When a vertex is toggled, that vertex and all adjacent vertices change their colors from \(0\) to \(1\) or vice-versa. The game is won when all vertices have color \(0\). The winnability of this game is related to the existence of a parity dominating set.
We generalize this game to \(\mathbb{Z}_k\), \(k \geq 2\), and use this to define a generalization of parity dominating sets. We determine all paths, cycles, and complete bipartite graphs in which the game over \(\mathbb{Z}_k\) can be won regardless of the initial coloring, and we determine a constructive method for creating all caterpillar graphs in which the Lights Out game cannot always be won.

A total coloring of a simple graph \(G\) is a coloring of both the edges and the vertices. A total coloring is proper if no two adjacent or incident elements receive the same color.The minimum number of colors required for a proper total coloring of \(G\) is called the total chromatic number of \(G\) and denoted by \(\chi_t(G)\). The Total Coloring Conjecture (TCC) states that for every simple graph \(G\),\(\Delta(G) + 1 \leq \chi_t(G) \leq \Delta(G) + 2.\) \(G\) is called Type \(1\) (resp. Type \(2\)) if \(\chi_t(G) = \Delta(G) +1\) (resp. \(\chi_t(G) = \Delta(G) + 2\)). In this paper, we prove that the folded hypercubes \(FQ_n\), is of Type \(1\) when \(n \geq 4\).

Let \(H\) be a simple graph with \(n\) vertices and \(\mathcal{G} = \{G_1, G_2, \ldots, G_n\}\) be a sequence of \(n\) rooted graphs.
Following Godsil and McKay (Bull. Austral. Math. Soc. \(18 (1978) 21-28\)) defined the the rooted product \(H({G})\) of \(H\) by \({G}\) is defined by identifying the root of \(G_i\) with the \(i\)th vertex of \(H\).In this paper, we calculate the Wiener index of \(H({G})\), i.e., the sum of distances between all pairs of vertices, in terms of the Wiener indices of \(G_i\), \(i = 1, 2, \ldots, k\).As an application, we derive a recursive relation for computing the Wiener index of Generalized Bethe trees.

Let \(G\) be a connected graph with \(p\) vertices and \(q\) edges.A \(\gamma\)-labeling of \(G\) is a one-to-one function f from \(V(G)\) to \({0,1,…,q}\) that induces a labeling \(f’\) from \(V(G)\) to \({1,2,…,q}\) defined by \(f(e) = |f(u) – f(v)|\) for each edge \(e = uv\) of \(G\). The value of a \(\gamma\)-labeling \(f\) is defined to be the sum of the values of \(f’\) over all
edges. Also, the maximum value of a \(\gamma\)-labeling of \(G\) is defined as the maximum of the values among all \(\gamma\)-labelings of \(G,\) while the minimum value is the minimum of the values among all \(\gamma\)-labelings
of \(G\). In this paper, the maximum value and minimum value are determined for any complete bipartite graph.

A labeling f of a graph G is a bijection from its edge set \(E(G)\) to the set \(\{1, 2, …, |E(G)|\}\), which is antimagic if for any distinct vertices \(x\) and \(y\), the sum of the labels on edges incident to \(x\) is different from the sum of the labels on edges incident to \(y\). A graph G is antimagic if \(G\) has an f which is antimagic. Hartsfield and Ringel conjectured in \(1990\)
that every connected graph other than Ko is antimagic. In this paper, we show that some graphs with regular subgraphs are antimagic.

In \([1]\), the author provided a Gray code for the set of \(n\)-length permutations with a given number of left-to-right minima in in-version array representation. In this paper, we give the first Gray code for the set of \(n\)-length permutations with a given number of left-to-right minima in one-line representation. In this code, each permutation is transformed into its successor by a product with a transposition or a cycle of length three. Also a generating algorithm for this code is given.

We introduce a generalization of the well-known concept of graceful labeling. Given a graph \(\Gamma\) with \(e = d.m\) edges, we define a \(d\)-graceful labeling of \(G\) as an injective function \(f: V(G) \rightarrow \{0, 1, 2, \ldots, d(m+1) – 1\}\) such that \(\{|f(x) – f(y)| : \{x, y\} \in E(\Gamma)\}\) = \(\{1, 2, 3, \ldots, d(m+1) – 1\} – \{m+1, 2(m+1), \ldots, (d-1)(m+1)\}.\) In the case of \(d = 1\) and of \(d = e\) we find the classical notion of a graceful labeling and of an odd graceful labeling, respectively.Also, we call \(d\)-graceful \(\alpha\)-labeling of a bipartite graph \(\Gamma\) a \(d\)-graceful labeling of \(\Gamma\) with the property that its maximum value on one of the two bipartite sets does not reach its minimum value on the other
one. We show that these new concepts allow to obtain certain cyclic graph decompositions. We investigate the existence of \(d\)-graceful \(\alpha\)-labelings for several classes of bipartite graphs, completely solving the problem for paths and stars and giving partial results about cycles of even length and ladders.