By h(G,x) and P(G,λ) we denote the adjoint polynomial and the chromatic polynomial of graph G, respectively. A new invariant of graph G, which is the fourth character R₄(G), is given in this paper. Using the properties of the adjoint polynomials, the adjoint equivalence class of graph $B_{n-6,1,2}$ is determined, which can be regarded as the continuance of the paper written by Wang et al. [J. Wang, R. Liu, C. Ye and Q. Huang, A complete solution to the chromatic equivalence class of graph $\overline{B_{n-7,1,3}}$, Discrete Math....

We study problems related to the chromatic number of a random intersection graph G (n,m, p). We introduce two new algorithms which colour G (n,m, p) with almost optimum number of colours with probability tending to 1 as n → ∞. Moreover we find a range of parameters for which the chromatic number of G (n,m, p) asymptotically equals its clique number.

One consequence of Hedetniemi’s conjecture on the chromatic number of the product of graphs is that the bound $\chi (G\times H)\ge min\{{\chi }_f\left(G\right),{\chi }_f\left(H\right)\}$ should always hold. We prove that $\chi (G\times H)\ge \frac{1}{2}min\{{\chi }_f\left(G\right),{\chi }_f\left(H\right)\}$.

In this note, all chromatic equivalence classes for 2-connected 3-chromatic graphs with five triangles and cyclomatic number six are described. New families of chromatically unique graphs of order n are presented for each n ≥ 8. This is a generalization of a result stated in [5]. Moreover, a proof for the conjecture posed in [5] is given.

Let G be a 2-connected graph of order n satisfying α(G) = a ≤ κ(G), where α(G) and κ(G) are the independence number and the connectivity of G, respectively, and let r(m,n) denote the Ramsey number. The well-known Chvátal-Erdös Theorem states that G has a hamiltonian cycle. In this paper, we extend this theorem, and prove that G has a 2-factor with a specified number of components if n is sufficiently large. More precisely, we prove that (1) if n ≥ k·r(a+4, a+1), then G has a 2-factor with k components,...

We take as given a real symmetric matrix A, whose graph is a tree T, and the eigenvalues of A, with their multiplicities. Each edge of T may then be classified in one of four categories, based upon the change in multiplicity of a particular eigenvalue, when the edge is removed (i.e. the corresponding entry of A is replaced by 0).We show a necessary and suficient condition for each possible classification of an edge. A special relationship is observed among 2-Parter edges, Parter edges and singly...

A digraph is associated with a finite group by utilizing the power map $f:G\to G$ defined by $f\left(x\right)=x^k$ for all $x\in G$, where $k$ is a fixed natural number. It is denoted by ${\gamma }_G(n,k)$. In this paper, the generalized quaternion and $2$-groups are studied. The height structure is discussed for the generalized quaternion. The necessary and sufficient conditions on a power digraph of a $2$-group are determined for a $2$-group to be a generalized quaternion group. Further, the classification of two generated $2$-groups as abelian or non-abelian...

Let $\Delta$ be a pure simplicial complex on the vertex set $\left[n\right]=\{1,...,n\}$ and $I_{\Delta }$ its Stanley-Reisner ideal in the polynomial ring $S=K[x_1,...,x_n]$. We show that $\Delta$ is a matroid (complete intersection) if and only if $S/I_{\Delta }^{\left(m\right)}$ ($S/I_{\Delta }^m$) is clean for all $m\in \mathbb{N}$ and this is equivalent to saying that $S/I_{\Delta }^{\left(m\right)}$ ($S/I_{\Delta }^m$, respectively) is Cohen-Macaulay for all $m\in \mathbb{N}$. By this result, we show that there exists a monomial ideal $I$ with (pretty) cleanness property while $S/I^m$ or $S/I^{\left(m\right)}$ is not (pretty) clean for all integer $m\ge 3$. If $dim\left(\Delta \right)=1$, we also prove that $S/I_{\Delta }^{\left(2\right)}$ ($S/I_{\Delta }^2$) is clean if and only if $S/I_{\Delta }^{\left(2\right)}$ ($S/I_{\Delta }^2$,...

A set D of vertices in a graph G = (V,E) is a dominating set of G if every vertex in V-D is adjacent to some vertex in D. The domination number γ(G) of G is the minimum cardinality of a dominating set. We define the cobondage number $b_c\left(G\right)$ of G to be the minimum cardinality among the sets of edges X ⊆ P₂(V) - E, where P₂(V) = X ⊆ V:|X| = 2 such that γ(G+X) < γ(G). In this paper, the exact values of bc(G) for some standard graphs are found and some bounds are obtained. Also, a Nordhaus-Gaddum type...

We consider directed figures defined as labelled polyominoes with designated start and end points, with two types of catenation operations. We are especially interested in codicity verification for sets of figures, and we show that depending on the catenation type the question whether a given set of directed figures is a code is decidable or not. In the former case we give a constructive proof which leads to a straightforward algorithm.

We consider directed figures defined as labelled polyominoes with designated start and end points, with two types of catenation operations. We are especially interested in codicity verification for sets of figures, and we show that depending on the catenation type the question whether a given set of directed figures is a code is decidable or not. In the former case we give a constructive proof which leads to a straightforward algorithm.