For a simple graph on vertices and an integer with , denote by the sum of largest signless Laplacian eigenvalues of . It was conjectured that , where is the number of edges of . This conjecture has been proved to be true for all graphs when , and for trees, unicyclic graphs, bicyclic graphs and regular graphs (for all ). In this note, this conjecture is proved to be true for all graphs when , and for some new classes of graphs.
In this paper, we give a generalization of a result of Lovasz from [2].
So far, the smallest complete bipartite graph which was known to have a cyclic decomposition into cubes of a given dimension d was . We improve this result and show that also allows a cyclic decomposition into . We also present a cyclic factorization of into Q₄.
The paper brings explicit formula for enumeration of vertex-labeled split graphs with given number of vertices. The authors derive this formula combinatorially using an auxiliary assertion concerning number of split graphs with given clique number. In conclusion authors discuss enumeration of vertex-labeled bipartite graphs, i.e., a graphical class defined in a similar manner to the class of split graphs.
In this paper, we show that the maximal number of minimal colourings of a graph with vertices and the chromatic number is equal to , and the single graph for which this bound is attained consists of a -clique and isolated vertices.
A Γ-distance magic labeling of a graph G = (V, E) with |V| = n is a bijection ℓ from V to an Abelian group Γ of order n such that the weight of every vertex x ∈ V is equal to the same element µ ∈ Γ, called the magic constant. A graph G is called a group distance magic graph if there exists a Γ-distance magic labeling for every Abelian group Γ of order |V(G)|. In this paper we give necessary and sufficient conditions for complete k-partite graphs of odd order p to be ℤp-distance magic. Moreover...