Let $G=(V_G,E_G)$ be a graph and let $N_G\left[v\right]$ denote the closed neighbourhood of a vertex $v$ in $G$. A function $f:V_G\to \{-1,0,1\}$ is said to be a balanced dominating function (BDF) of $G$ if ${\sum }_{u\in N_G\left[v\right]}f\left(u\right)=0$ holds for each vertex $v\in V_G$. The balanced domination number of $G$, denoted by ${\gamma }_b\left(G\right)$, is defined as $${\gamma }_b\left(G\right)=max\left\{\sum _{v\in V_G}f\left(v\right):f\text{is}\text{a}\text{BDF}\text{of}G\right\}.$$ A graph $G$ is called $d$-balanced if ${\gamma }_b\left(G\right)=0$. The novel concept of balanced domination for graphs is introduced. Some upper bounds on the balanced domination number are established, in which one is the best possible bound and the rest are sharp, all the corresponding...

A construction of a minimum cycle bases for the wreath product of some classes of graphs is presented. Moreover, the basis numbers for the wreath product of the same classes are determined.

For any graph $G$, let $V\left(G\right)$ and $E\left(G\right)$ denote the vertex set and the edge set of $G$ respectively. The Boolean function graph $B(G,L(G),\mathrm{N}INC)$ of $G$ is a graph with vertex set $V\left(G\right)\cup E\left(G\right)$ and two vertices in $B(G,L(G),\mathrm{N}INC)$ are adjacent if and only if they correspond to two adjacent vertices of $G$, two adjacent edges of $G$ or to a vertex and an edge not incident to it in $G$. For brevity, this graph is denoted by $B_1\left(G\right)$. In this paper, structural properties of $B_1\left(G\right)$ and its complement including traversability and eccentricity properties are studied. In addition,...

Let ${\mu }_{n-1}\left(G\right)$ be the algebraic connectivity, and let ${\mu }_1\left(G\right)$ be the Laplacian spectral radius of a $k$-connected graph $G$ with $n$ vertices and $m$ edges. In this paper, we prove that $${\mu }_{n-1}\left(G\right)\ge \frac{2n{k}^2}{(n(n-1)-2m)(n+k-2)+2k^2},$$ with equality if and only if $G$ is the complete graph $K_n$ or $K_n-e$. Moreover, if $G$ is non-regular, then $${\mu }_1\left(G\right)<2\Delta -\frac{2(n\Delta -2m)k^2}{2(n\Delta -2m)(n^2-2n+2k)+n{k}^2},$$ where $\Delta$ stands for the maximum degree of $G$. Remark that in some cases, these two inequalities improve some previously known results.

We use an algebraic method to classify the generalized permutation star-graphs, and we use the classification to determine the toughness of all generalized permutation star-graphs.

Homotopic methods are employed for the characterization of the complete digraphs which are the composition of non-trivial highly regular tournaments.

Let ₁,₂ be additive hereditary properties of graphs. A (₁,₂)-decomposition of a graph G is a partition of E(G) into sets E₁, E₂ such that induced subgraph $G\left[E_i\right]$ has the property ${}_i$, i = 1,2. Let us define a property ₁⊕₂ by G: G has a (₁,₂)-decomposition. A property D is said to be decomposable if there exists nontrivial additive hereditary properties ₁, ₂ such that D = ₁⊕₂. In this paper we determine the completeness of some decomposable properties and we characterize the decomposable properties of completeness...