For any graph $G=(V,E)$, a subset $S\subseteq V$ is called {\it an isolating set} of $G$ if $V\setminus N_G[S]$ independent set $G$, where $N_G[S]=S\cup N_G(S)$, and the isolation number} denoted by $\iota(G)$, size smallest $G$. In this article, we show that number middle equal to maximal matching

A graph is called {\it NIC-planar} if it admits a drawing in the plane such that each edge crossed at most once and two pairs of crossing edges share one vertex. together with NIC-planar NIC-plane graph}. maximal no new can be added so resulting still NIC-plane. In this paper, we show any order $n$ minimum degree least $3$ has $\frac{7}{3}n-\frac{10}{3}$ edges, $\frac{11}{5}n-\frac{18}{5}$ edges. Moreover, both lower bounds are tight for infinitely many positive integers $n$.

In his article [J. Comb. Theory Ser. B 16 (1974), 168-174], Tutte called two graphs $T$-equivalent (i.e., codichromatic) if they have the same polynomial and showed that $G$ $G'$ are is obtained from by flipping a rotor replacing it its mirror) of order at most $5$, where $k$ in an induced subgraph $R$ having automorphism $\psi$ with vertex orbit $\{\psi^i(u): i\ge 0\}$ size such every only adjacent to vertices unless this orbit. article, we first show above result due can be extended $k\ge...

A 1-plane graph is a together with drawing in the plane such way that each edge crossed at most once. maximal if no can be added without violating either 1-planarity or simplicity. Let $m(n)$ denote minimum size of $1$-plane order $n$. Brandenburg et al. established $m(n)\ge 2.1n-\frac{10}{3}$ for all $n\ge 4$, which was improved by Bar\'{a}t and T\'{o}th to \frac{20}{9}n-\frac{10}{3}$. In this paper, we confirm $m(n)=\left\lceil\frac{7}{3}n\right\rceil-3$ 5$.

For any graph $G$, let $t(G)$ be the number of spanning trees $L(G)$ line $G$ and for non-negative integer $r$, $S_r(G)$ obtained from by replacing each edge $e$ a path length $r+1$ connecting two ends $e$. In this paper we obtain an expression $t(L(S_r(G)))$ in terms combinatorial approach. This result generalizes some known results on relation between gives explicit $t(L(S_r(G)))=k^{m+s-n-1}(rk+2)^{m-n+1}t(G)$ if is order $n+s$ size $m+s$ which $s$ vertices are degree $1$ others $k$. Thus...

Abstract In this article, we extend Moon's classic formula for counting spanning trees in complete graphs containing a fixed forest to bipartite graphs. Let be the bipartition of graph with and . We prove that any given components , number which contain all edges is equal where

In this paper, we present a formula for computing the Tutte polynomial of signed graph formed from labeled by edge replacements in terms chain graph. Then define family 'ring tangles' links and consider zeros their Jones polynomials. By applying obtained, Beraha-Kahane-Weiss's theorem Sokal's lemma, prove that polynomials (pretzel) are dense whole complex plane.

Let $\theta(a_1,a_2,\cdots,a_k)$ denote the graph obtained by connecting two distinct vertices with $k$ independent paths of lengths $a_1,a_2,$ $\cdots,a_k$ respectively. Assume that $2\le a_1\le a_2\le \cdots \le a_k$. We prove $\theta(a_1,a_2, \cdots,a_k)$ is chromatically unique if $a_k < a_1+a_2$, and find examples showing may not be $a_k=a_1+a_2$.

Let be a nonseparable plane graph on vertices with at least two edges. Suppose that has outer face and every 2-vertex-cut of contains one vertex . denote the chromatic polynomial We show for all This result is corollary more general , where multivariate Tutte which are not incident to other edges suitably chosen intervals