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_-(A) \le n+1$ to allow orthogonality.
The independent domination number $i(G)$ (independent number $\beta (G)$) 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(G)\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(S_{m}(k,l))$ and prove that if $k+l=m$ then Haviland’s conjecture holds for the subset graph $S_{m}(k,l)$. Furthermore, we give the exact value of $\beta (S_{m}(k,l))$.
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 (G)$, is the minimum cardinality of a dominating set. In this paper we will prove that if $G$ is a 5-regular graph, then $\gamma (G)\le {5\over 14}n$.
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}(G)$. 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}(G)=k$ and $\gamma _{c}(G+e)<k$ for each edge $e\in E(H)$. First, we discuss some classes of graphs whether they are $\gamma _{c}$-critical relative to $K_{s,s}$. Then we study $k$-$\gamma _{c}$-critical graphs relative to $K_{s,s}$ for small values of $k$. In particular, we characterize the $3$-$\gamma _{c}$-critical and $4$-$\gamma _{c}$-critical graphs.
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\geq 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 $t\geq 3$ and any odd integer $k \geq 2t+1$, if a $k$-connected graph $G$ contains neither $K_{1}+(K_{2}\cup K_{1, t})$, nor $K_{1}+(2K_{2}\cup K_{1, 2})$, then $G$ has a $k$-contractible edge.
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 (G)$. The domination number, denoted by $\gamma (G)$, 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 (G) \le \frac{4}{11}n$.
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(v)$, is the set $N_k(v)=\lbrace u\mid u\ne v$ and $d(u,v)\le k\rbrace $. $N_k[v]=N_k(v)\cup \lbrace v\rbrace $ is the closed $k$-neighborhood of $v$. A function $f\: V\rightarrow \lbrace -1,1\rbrace $ is a signed distance-$k$-dominating function of $G$, if for every vertex $v\in V$, $f(N_k[v])=\sum _{u\in N_k[v]}f(u)\ge 1$. The signed distance-$k$-domination number, denoted by $\gamma _{k,s}(G)$, is the minimum weight of a signed distance-$k$-dominating function on $G$. The values of $\gamma _{2,s}(G)$ are found for graphs with small diameter, paths, circuits. At the end it is proved that $\gamma _{2,s}(T)$ is not bounded from below in general for any tree $T$.
We initiate the study of signed majority total domination in graphs. Let $G=(V,E)$ be a simple graph. For any real valued function $f\: V \rightarrow \mathbb{R}$ and ${S\subseteq V}$, let $f(S)=\sum _{v\in S}f(v)$. A signed majority total dominating function is a function $f\: V\rightarrow \lbrace -1,1\rbrace $ such that $f(N(v))\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 maj}}^{{\,\mathrm t}}(G)=\min \lbrace f(V)\mid f$ is a signed majority total dominating function on $G\rbrace $. We research some properties of the signed majority total domination number of a graph $G$ and obtain a few lower bounds of $\gamma _{{\mathrm maj}}^{{\,\mathrm t}}(G)$.
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(G)$, is the smallest cardinality of a total restrained dominating set of $G$. First, some exact values and sharp bounds for $\gamma _r^t(G)$ are given in Section 2. Then the Nordhaus-Gaddum-type results for total restrained domination number are established in Section 3. Finally, we show that the decision problem for $\gamma _r^t(G)$ is NP-complete even for bipartite and chordal graphs in Section 4.