Search

• We observed that any maximal 1-plane graph with at most 6 dominating vertices. Then they provided a nice characterization for the structure for any maximal 1-plane graph with k dominating vertices for k = 3; 4; 5; 6. • For the maximal 1-plane graphs with 2 dominating vertices, we obtained tight lower bounds for the number of edges of G. • In addition, we present similar results for maximal 1-plane graphs with 1 dominating vertex. The new (nice) results here settle the open problem of Ouyang et al. in [Applied Mathematics and Computation 362:124537, 2019]. A graph G is called 1-planar if it can be drawn in the plane so that each edge is crossed by at most one other edge. A graph, together with a 1-planar drawing is called 1-plane. A graph is maximal 1- planar (1-plane), if we cannot add any missing edge so that the resulting graph is still 1-planar (1-plane). Let G be a maximal 1-plane graph of order n and k dominating vertices. In this paper, we first provide a complete characterization on G for 3 ≤ k ≤ 6. Then we prove that G has at least 5 2 n − 4 edges for k = 2 , and this bound is tight. Finally, we obtain that G has at least 7 3 n − 10 3 edges for k = 1. Our results also settle an open problem posed by Ouyang et al. in [Applied Mathematics and Computation 362:124537, 2019]. [ABSTRACT FROM AUTHOR]

Abstract: A stable set of a graph is a vertex set in which any two vertices are not adjacent. It was proven in [A. Brandstädt, V.B. Le, T. Szymczak, The complexity of some problems related to graph 3-colorability, Discrete Appl. Math. 89 (1998) 59–73] that the following problem is NP-complete: Given a bipartite graph G, check whether G has a stable set S such that is a tree. In this paper we prove the following problem is polynomially solvable: Given a graph G with maximum degree 3 and containing no vertices of degree 2, check whether G has a stable set S such that is a tree. Thus we partly answer a question posed by the authors in the above paper. Moreover, we give some structural characterizations for a graph G with maximum degree 3 that has a stable set S such that is a tree. [Copyright &y& Elsevier]

Let K 5 , n + 1 ∖ e (n ≥ 0) denote the complete bipartite graph K 5 , n + 1 with one edge deleted. In this paper, we show that the crossing number of K 5 , n + 1 ∖ e is n (n − 1). [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we determine the crossing number of by the construction method for and apply the zip product to obtain that for . Furthermore, we have for , , which is consistent with Zheng’s conjecture for the crossing number of . [Copyright &y& Elsevier]