Search

Let Gbe a graph and v∈V(G). The neighbors of v, denoted by N(v), are the set of vertices adjacent to v. Let N[v]=N(v)∪{v}and J(u,v)={w∈N(u)∩N(v):N(w)⊆N[u]∪N[v]}. A graph Gis called quasi-claw-free if J(u,v)≠∅for any u,v∈V(G)with d(u,v)=2. In this paper, we show that if Gis a connected quasi-claw-free graph with σk+1(G)≥|G|-k,then Gcontains a spanning k-ended tree, which generalizes some known results.

Let Sbe a finite set of positive integers. A mixed hypergraph ℋ is a onerealization of Sif its feasible set is Sand each entry of its chromatic spectrum is either 0 or 1. The minimum number of vertices, denoted by δ3(S), in a 3-uniform bi-hypergraph which is a one-realization of Swas determined in [P. Zhao, K. Diao and F. Lu, More result on the smallest one-realization of a given set, Graphs Combin. 32 (2016) 835–850]. In this paper, we consider the minimum number of edges in a 3-uniform bi-hypergraph which already has the minimum number of vertices with respect of being a minimum bihypergraph that is one-realization of S. A tight lower bound on the number of edges in a 3-uniform bi-hypergraph which is a one-realization of Swith δ3(S) vertices is given.

An orientation of a graph Gwith even number of vertices is Pfaffian if every even cycle Csuch that G − V(C) has a perfect matching has an odd number of edges directed in either direction of the cycle. The significance of Pfaffian orientations stems from the fact that if a graph Ghas one, then the number of perfect matchings of Gcan be computed in polynomial time. There is a classical result of Kasteleyn that every planar graph has a Pfaffian orientation. Little proved an elegant characterization of bipartite graphs that admit a Pfaffian orientation. Robertson, Seymour and Thomas (1999) gave a polynomial-time recognition algorithm to test whether a bipartite graph is Pfaffian by a structural description of bipartite graphs. In this paper, we consider the Pfaffian property of graphs embedding on the orientable surface with genus one (i.e., the torus). Some sufficient conditions for Pfaffian graphs on the torus are obtained. Furthermore, we show that all quadrilateral tilings on the torus are Pfaffian if and only if they are not bipartite graphs.