Advanced Search

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 simple graph. A subset $S\subseteq V$ is a dominating set of $G$, if for any vertex $v\in V-S$ there exists a vertex $u\in S$ such that $uv\in E\left(G\right)$. The domination number, denoted by $\gamma \left(G\right)$, is the minimum cardinality of a dominating set. In this paper we prove that if $G$ is a 4-regular graph with order $n$, then $\gamma \left(G\right)\le \frac{4}{11}n$.

An edge $e$ of a $k$-connected graph $G$ is said to be $k$-contractible (or simply contractible) if the graph obtained from $G$ by contracting $e$ (i.e., deleting $e$ and identifying its ends, finally, replacing each of the resulting pairs of double edges by a single edge) is still $k$-connected. In 2002, Kawarabayashi proved that for any odd integer $k\ge 5$, if $G$ is a $k$-connected graph and $G$ contains no subgraph $D=K_1+(K_2\cup K_{1,2})$, then $G$ has a $k$-contractible edge. In this paper, by generalizing this result, we prove that for any integer...

A dominating set in a graph $G$ is a connected dominating set of $G$ if it induces a connected subgraph of $G$. The minimum number of vertices in a connected dominating set of $G$ is called the connected domination number of $G$, and is denoted by ${\gamma }_c\left(G\right)$. Let $G$ be a spanning subgraph of $K_{s,s}$ and let $H$ be the complement of $G$ relative to $K_{s,s}$; that is, $K_{s,s}=G\oplus H$ is a factorization of $K_{s,s}$. The graph $G$ is $k$-${\gamma }_c$-critical relative to $K_{s,s}$ if ${\gamma }_c\left(G\right)=k$ and ${\gamma }_c(G+e)<k$ for each edge $e\in E\left(H\right)$. First, we discuss some classes of graphs whether they are ${\gamma }_c$-critical relative...

The signed distance-$k$-domination number of a graph is a certain variant of the signed domination number. If $v$ is a vertex of a graph $G$, the open $k$-neighborhood of $v$, denoted by $N_k\left(v\right)$, is the set $N_k\left(v\right)=\{u\mid u\ne v$ and $d(u,v)\le k\}$. $N_k\left[v\right]=N_k\left(v\right)\cup \left\{v\right\}$ is the closed $k$-neighborhood of $v$. A function $fV\to \{-1,1\}$ is a signed distance-$k$-dominating function of $G$, if for every vertex $v\in V$, $f\left(N_k\left[v\right]\right)={\sum }_{u\in N_k\left[v\right]}f\left(u\right)\ge 1$. The signed distance-$k$-domination number, denoted by ${\gamma }_{k,s}\left(G\right)$, is the minimum weight of a signed distance-$k$-dominating function on $G$. The values of ${\gamma }_{2,s}\left(G\right)$ are found for graphs with small diameter,...

In this paper we initiate the study of total restrained domination in graphs. Let $G=(V,E)$ be a graph. A total restrained dominating set is a set $S\subseteq V$ where every vertex in $V-S$ is adjacent to a vertex in $S$ as well as to another vertex in $V-S$, and every vertex in $S$ is adjacent to another vertex in $S$. The total restrained domination number of $G$, denoted by ${\gamma }_r^t\left(G\right)$, is the smallest cardinality of a total restrained dominating set of $G$. First, some exact values and sharp bounds for ${\gamma }_r^t\left(G\right)$ are given in Section 2. Then the Nordhaus-Gaddum-type...

We initiate the study of signed majority total domination in graphs. Let $G=(V,E)$ be a simple graph. For any real valued function $fV\to ℝ$ and $S\subseteq V$, let $f\left(S\right)={\sum }_{v\in S}f\left(v\right)$. A signed majority total dominating function is a function $fV\to \{-1,1\}$ such that $f\left(N\right(v\left)\right)\ge 1$ for at least a half of the vertices $v\in V$. The signed majority total domination number of a graph $G$ is ${\gamma }_{\mathrm{m}aj}^{\mathrm{t}}\left(G\right)=min\{f\left(V\right)\mid f$ is a signed majority total dominating function on $G\}$. We research some properties of the signed majority total domination number of a graph $G$ and obtain a few lower bounds of ${\gamma }_{\mathrm{m}aj}^{\mathrm{t}}\left(G\right)$.

A sign pattern $A$ is a $\pm$ sign pattern if $A$ has no zero entries. $A$ allows orthogonality if there exists a real orthogonal matrix $B$ whose sign pattern equals $A$. Some sufficient conditions are given for a sign pattern matrix to allow orthogonality, and a complete characterization is given for $\pm$ sign patterns with $n-1\le N_{-}\left(A\right)\le n+1$ to allow orthogonality.

Let $G=(V,E)$ be a simple graph. A subset $S\subseteq V$ is a dominating set of $G$, if for any vertex $u\in V-S$, there exists a vertex $v\in S$ such that $uv\in E$. The domination number, denoted by $\gamma \left(G\right)$, is the minimum cardinality of a dominating set. In this paper we will prove that if $G$ is a 5-regular graph, then $\gamma \left(G\right)\le \frac{5}{14}n$.

In this paper, we study the existence of nontrivial solutions to a class fractional Schrödinger equations (−Δ)su+V(x)u=λf(x,u)inRN, $${(-\Delta )}^{s}u+V\left(x\right)u=\lambda f(x,u)\mathrm{in}{ℝ}^N,$$ where [...] (−Δ)su(x)=2limε→0∫RN∖Bε(X)u(x)−u(y)|x−y|N+2sdy,x∈RN ${(-\Delta )}^{s}u\left(x\right)=2\underset{\epsilon \to 0}{lim}{\int }_{{ℝ}^N\setminus B_{\epsilon }\left(X\right)}\frac{u\left(x\right)-u\left(y\right)}{|x-y{|}^{N+2s}}dy,x\in {ℝ}^N$ is a fractional operator and s ∈ (0, 1). By using variational methods, we prove this problem has at least two nontrivial solutions in a suitable weighted fractional Sobolev space.

The independent domination number $i\left(G\right)$ (independent number $\beta \left(G\right)$) is the minimum (maximum) cardinality among all maximal independent sets of $G$. Haviland (1995) conjectured that any connected regular graph $G$ of order $n$ and degree $\delta \le \frac{1}{2}n$ satisfies $i\left(G\right)\le \lceil \frac{2n}{3\delta }\rceil \frac{1}{2}\delta$. For $1\le k\le l\le m$, the subset graph $S_m(k,l)$ is the bipartite graph whose vertices are the $k$- and $l$-subsets of an $m$ element ground set where two vertices are adjacent if and only if one subset is contained in the other. In this paper, we give a sharp upper bound for $i\left(S_m(k,l)\right)$ and prove that...