Let $G=(V,E)$ be a simple graph. A $3$-valued function $fV\left(G\right)\to \{-1,0,1\}$ is said to be a minus dominating function if for every vertex $v\in V$, $f\left(N\left[v\right]\right)={\sum }_{u\in N\left[v\right]}f\left(u\right)\ge 1$, where $N\left[v\right]$ is the closed neighborhood of $v$. The weight of a minus dominating function $f$ on $G$ is $f\left(V\right)={\sum }_{v\in V}f\left(v\right)$. The minus domination number of a graph $G$, denoted by ${\gamma }^{-}\left(G\right)$, equals the minimum weight of a minus dominating function on $G$. In this paper, the following two results are obtained. (1) If $G$ is a bipartite graph of order $n$, then $${\gamma }^{-}\left(G\right)\ge 4\left(\sqrt{n+1}-1\right)-n.$$ (2) For any negative integer $k$ and any positive integer $m\ge 3$, there exists...

Let $G$ be a connected graph of order $n$ and $U$ a unicyclic graph with the same order. We firstly give a sharp bound for $m_G\left(\mu \right)$, the multiplicity of a Laplacian eigenvalue $\mu$ of $G$. As a straightforward result, $m_U\left(1\right)\le n-2$. We then provide two graph operations (i.e., grafting and shifting) on graph $G$ for which the value of $m_G\left(1\right)$ is nondecreasing. As applications, we get the distribution of $m_U\left(1\right)$ for unicyclic graphs on $n$ vertices. Moreover, for the two largest possible values of $m_U\left(1\right)\in \{n-5,n-3\}$, the corresponding graphs $U$ are completely...

In this paper we investigate the effect on the multiplicity of Laplacian eigenvalues of two disjoint connected graphs when adding an edge between them. As an application of the result, the multiplicity of 1 as a Laplacian eigenvalue of trees is also considered.

We say that a graph G is maximal Kp-free if G does not contain Kp but if we add any new edge e ∈ E(G) to G, then the graph G + e contains Kp. We study the minimum and maximum size of non-(p − 1)-partite maximal Kp-free graphs with n vertices. We also answer the interpolation question: for which values of n and m are there any n-vertex maximal Kp-free graphs of size m?

We consider the nearest neighbor random walk on planar graphs. For certain families of these graphs, we give explicit upper bounds on the norm of the random walk operator in terms of the minimal number of edges at each vertex. We show that for a wide range of planar graphs the spectral radius of the random walk is less than one.

Let $G=(V,E)$ be a 3-connected planar graph, with $V=\{1,...,n\}$. Let $M=\left(m_{i,j}\right)$ be a symmetric $n\times n$ matrix with exactly one negative eigenvalue (of multiplicity 1), such that for $i,j$ with $i\ne j$, if $i$ and $j$ are adjacent then $m_{i,j}\<0$ and if $i$ and $j$ are nonadjacent then $m_{i,j}=0$, and such that $M$ has rank $n-3$. Then the null space $kerM$ of $M$ gives an embedding of $G$ in $S^2$ as follows: let $\{a,b,c\}$ be a basis of $kerM$, and for $i\in V$ let $\varphi \left(i\right):=(a_i,b_i,c_i{)}^T$; then $\varphi \left(i\right)\ne 0$, and $\psi \left(i\right):=\varphi \left(i\right)/\parallel \varphi \left(i\right)\parallel$ embeds $V$ in $S^2$ such that connecting, for any two adjacent vertices $i,j$, the points $\psi \left(i\right)$ and $\psi \left(j\right)$ by a shortest geodesic on $S^2$, gives...