A subset $S$ of vertices in a graph $G$ is an open packing set if no pair of vertices of $S$ has a common neighbor in $G$. An open packing set which is not a proper subset of any open packing set is called a maximal open packing set. The maximum cardinality of an open packing set is called the open packing number and is denoted by ${\rho }^{\mathrm{o}}\left(G\right)$. A subset $S$ in a graph $G$ with no isolated vertex is called a total dominating set if any vertex of $G$ is adjacent to some vertex of $S$. The total domination number of $G$, denoted...

It is well-known that any graph has all real eigenvalues and a graph is bipartite if and only if its spectrum is symmetric with respect to the origin. We are interested in finding whether the permanental roots of a bipartite graph G have symmetric property as the spectrum of G. In this note, we show that the permanental roots of bipartite graphs are symmetric with respect to the real and imaginary axes. Furthermore, we prove that any graph has no negative real permanental root, and any graph containing...

We give a lower bound for the Ramsey number and the planar Ramsey number for C₄ and complete graphs. We prove that the Ramsey number for C₄ and K₇ is 21 or 22. Moreover we prove that the planar Ramsey number for C₄ and K₆ is equal to 17.

For graphs $G$, $F_1$, $F_2$, we write $G\to (F_1,F_2)$ if for every red-blue colouring of the edge set of $G$ we have a red copy of $F_1$ or a blue copy of $F_2$ in $G$. The size Ramsey number $\widehat{r}(F_1,F_2)$ is the minimum number of edges of a graph $G$ such that $G\to (F_1,F_2)$. Erdős and Faudree proved that for the cycle $C_n$ of length $n$ and for $t\ge 2$ matchings $t{K}_2$, the size Ramsey number $\widehat{r}(t{K}_2,C_n)<n+(4t+3)\sqrt{n}$. We improve their upper bound for $t=2$ and $t=3$ by showing that $\widehat{r}(2K_2,C_n)\le n+2\sqrt{3n}+9$ for $n\ge 12$ and $\widehat{r}(3K_2,C_n)<n+6\sqrt{n}+9$ for $n\ge 25$.

Let $T_{s}H$ be the graph obtained from a given graph $H$ by subdividing each edge $s$ times. Motivated by a problem raised by Igor Pak [Mixing time and long paths in graphs, in Proc. of the 13th annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2002) 321–328], we prove that, for any graph $H$, there exist graphs $G$ with $O\left(s\right)$ edges that are Ramsey with respect to $T_{s}H$.

Let TsH be the graph obtained from a given graph H by subdividing each edge s times. Motivated by a problem raised by Igor Pak [Mixing time and long paths in graphs, in Proc. of the 13th annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2002) 321–328], we prove that, for any graph H, there exist graphs G with O(s) edges that are Ramsey with respect to TsH.

An independent set S of a graph G is said to be essential if S has a pair of vertices that are distance two apart in G. In 1994, Song and Zhang proved that if for each independent set S of cardinality k+1, one of the following condition holds: (i) there exist u ≠ v ∈ S such that d(u) + d(v) ≥ n or |N(u) ∩ N(v)| ≥ α (G); (ii) for any distinct u and v in S, |N(u) ∪ N(v)| ≥ n - max{d(x): x ∈ S}, then G is Hamiltonian. We prove that if for each essential...

Let G be a connected graph of size at least 2 and c :E(G)→{0, 1, . . . , k− 1} an edge coloring (or labeling) of G using k labels, where adjacent edges may be assigned the same label. For each vertex v of G, the color code of v with respect to c is the k-vector code(v) = (a0, a1, . . . , ak−1), where ai is the number of edges incident with v that are labeled i for 0 ≤ i ≤ k − 1. The labeling c is called a detectable labeling if distinct vertices in G have distinct color codes. The value val(c) of...

In this note we present some sufficient conditions for the uniqueness of a stable matching in the Gale-Shapley marriage classical model of even size. We also state the result on the existence of exactly two stable matchings in the marriage problem of odd size with the same conditions.

Let G be a 2-connected planar graph with maximum degree Δ such that G has no cycle of length from 4 to k, where k ≥ 4. Then the total chromatic number of G is Δ +1 if (Δ,k) ∈ {(7,4),(6,5),(5,7),(4,14)}.

Erratum Identification and corrections of the existing mistakes in the paper On the total graph of Mycielski graphs, central graphs and their covering numbers, Discuss. Math. Graph Theory 33 (2013) 361-371.