The bipartite Ramsey numbers.
The block connectivity of random trees.
The block plan problem. A graphtheoretic approach
The bondage number of graphs: good and bad vertices
The domination number γ(G) of a graph G is the minimum number of vertices in a set D such that every vertex of the graph is either in D or is adjacent to a member of D. Any dominating set D of a graph G with |D| = γ(G) is called a γ-set of G. A vertex x of a graph G is called: (i) γ-good if x belongs to some γ-set and (ii) γ-bad if x belongs to no γ-set. The bondage number b(G) of a nonempty graph G is the cardinality of a smallest set of edges whose removal from G results in a graph with domination...
The Borodin-Kostochka conjecture for graphs containing a doubly critical edge.
The -algebras of row-finite graphs.
The Cayley graph and the growth of Steiner loops
We study properties of Steiner loops which are of fundamental importance to develop a combinatorial theory of loops along the lines given by Combinatorial Group Theory. In a summary we describe our findings.
The Cayley graphs of and the limits of vertex-primitive graphs of -type.
The characteristic polynomial of a graph is reconstructible from the characteristic polynomials of its vertex-deleted subgraphs and their complements.
The chromatic equivalence class of graph
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 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 , Discrete Math....
The chromatic index of cyclic Steiner 2-designs.
The Chromatic Number of a Class of Pseudo-2-Manifolds.
The chromatic number of extended odd graphs is four
The Chromatic Number of Random Intersection Graphs
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.
The chromatic number of the product of two graphs is at least half the minimum of the fractional chromatic numbers of the factors
One consequence of Hedetniemi’s conjecture on the chromatic number of the product of graphs is that the bound should always hold. We prove that .
The chromatic sum of a graph: history and recent developments.
The chromaticity of a family of 2-connected 3-chromatic graphs with five triangles and cyclomatic number six
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.
The Chvátal-Erdős condition and 2-factors with a specified number of components
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,...
The circular chromatic index of flower snarks.
The classification of edges and the change in multiplicity of an eigenvalue of a real symmetric matrix resulting from the change in an edge value
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...