Two decades ago, resistance distance was introduced to characterize “chemical distance” in (molecular) graphs. In this paper, we consider three resistance distance-based graph invariants, namely, the Kirchhoff index, the additive degree-Kirchhoff index, and the multiplicative degree-Kirchhoff index. Some Nordhaus-Gaddum-type results for these three molecular structure descriptors are obtained. In addition, a relation between these Kirchhoffian indices is established.

For a simple graph $G$ on $n$ vertices and an integer $k$ with $1\le k\le n$, denote by ${𝒮}_k^{+}\left(G\right)$ the sum of $k$ largest signless Laplacian eigenvalues of $G$. It was conjectured that ${𝒮}_k^{+}\left(G\right)\le e\left(G\right)+\left(\genfrac{}{}{0pt}{}{k+1}{2}\right)$, where $e\left(G\right)$ is the number of edges of $G$. This conjecture has been proved to be true for all graphs when $k\in \{1,2,n-1,n\}$, and for trees, unicyclic graphs, bicyclic graphs and regular graphs (for all $k$). In this note, this conjecture is proved to be true for all graphs when $k=n-2$, 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 $Q_d$ of a given dimension d was $K_{d{2}^{d-1},d{2}^{d-2}}$. We improve this result and show that also $K_{d{2}^{d-2},d{2}^{d-2}}$ allows a cyclic decomposition into $Q_d$. We also present a cyclic factorization of $K_{8,8}$ 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 $n$ vertices and the chromatic number $k$ is equal to $k^{n-k}$, and the single graph for which this bound is attained consists of a $k$-clique and $n-k$ 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 $$w\left(x\right)={\sum }_{y\in N_G\left(x\right)}\ell \left(y\right)$$ 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...

A graph $G=(V,E)$ is called improperly $(d_1,\cdots ,d_k)$-colorable if the vertex set $V$ can be partitioned into subsets $V_1,\cdots ,V_k$ such that the graph $G\left[V_i\right]$ induced by the vertices of $V_i$ has maximum degree at most $d_i$ for all $1\le i\le k$. In this paper, we mainly study the improper coloring of $1$-planar graphs and show that $1$-planar graphs with girth at least $7$ are $(2,0,0,0)$-colorable.

Let the number of $k$-element sets of independent vertices and edges of a graph $G$ be denoted by $n(G,k)$ and $m(G,k)$, respectively. It is shown that the graphs whose every component is a circuit are the only graphs for which the equality $n(G,k)=m(G,k)$ is satisfied for all values of $k$.

In this paper we characterize $k$-chromatic graphs without isolated vertices and connected $k$-chromatic graphs having a minimal number of edges.