Advanced Search

Several matrices can be associated to a graph, such as the adjacency matrix or the Laplacian matrix. The spectrum of these matrices gives some informations about the structure of the graph and the question “Which graphs are determined by their spectrum?” is still a difficult problem in spectral graph theory. Let [...] p2q ${𝒰}_p^{2q}$ be the set of graphs obtained from Cp by attaching two pendant edges to each of q (q ⩽ p) vertices on Cp, whereas [...] p2q ${𝒱}_p^{2q}$ the subset of [...] p2q ${𝒰}_p^{2q}$ with odd p and its q vertices...

Sharp bounds on some distance-based graph invariants of $n$-vertex $k$-trees are established in a unified approach, which may be viewed as the weighted Wiener index or weighted Harary index. The main techniques used in this paper are graph transformations and mathematical induction. Our results demonstrate that among $k$-trees with $n$ vertices the extremal graphs with the maximal and the second maximal reciprocal sum-degree distance are coincident with graphs having the maximal and the second maximal reciprocal...

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...