Search

An edge e in a matching covered graph G is removable if G - e is matching covered. Removable edges were introduced by Lovász and Plummer in connection with ear decompositions of matching covered graphs. A brick is a non-bipartite matching covered graph without non-trivial tight cuts. The importance of bricks stems from the fact that they are building blocks of matching covered graphs. Lovász proved that every brick other than K 4 and C 6 ¯ has a removable edge. It is known that every 3-connected claw-free graph with even number of vertices is a brick. By characterizing the structure of adjacent non-removable edges, we show that every claw-free brick G with more than 6 vertices has at least 5|V(G)|/8 removable edges. [ABSTRACT FROM AUTHOR]

A graph without induced subgraphs isomorphic to a path of length 3 is P 4 -free. If a graph G contains two spanning trees T 1 , T 2 such that for each two distinct vertices x, y of G, the (x, y)-path in each T i has no common edge and no common vertex except for the two ends, then T 1 , T 2 are called two completely independent spanning trees (CISTs) of G , i ∈ { 1 , 2 }. Several results have shown that some sufficient conditions for Hamiltonian graphs may also guarantee the existence of two CISTs. Jung proved that a P 4 -free graph with at least 3 vertices is Hamiltonian if and only if it is 1-tough. Inspired by these results, in this paper, we prove that a P 4 -free graph G contains two CISTs if and only if G is a 2-connected graph of order n ≥ 4 and G ∉ K , where K is a family of some graphs. Moreover, we obtain that every 1-tough P 4 -free graph of order n ≥ 4 with G ∉ K ′ contains two CISTs, where K ′ is a family of four graphs. [ABSTRACT FROM AUTHOR]

Let G be 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 G is 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 G is a connected quasi-claw-free graph with σ k + 1 (G) ≥ | G | - k , then G contains a spanning k-ended tree, which generalizes some known results. [ABSTRACT FROM AUTHOR]

Let S={n1,n2,…,ns}, s≥2, be a set of positive integers. A mixed hypergraph H=(X,C,D) is a one-realization of S if for every i∈S, there exists a unique coloring (up to permutations of the colors) using precisely i colors and there are no other colorings.For any r≥3 and set of integers S, we show that any r-uniform one-realization of S is isomorphic to a subhypergraph of Hn1,…,ns2 which is a special r-uniform one-realization of S. [ABSTRACT FROM AUTHOR]

A color-bounded hypergraph is a hypergraph with vertex set X and edge set $${\mathcal {E}}=\{E_1,E_2,\dots ,E_m\}$$ , together with integers $$s_i$$ and $$t_i$$ ( $$1\le s_i\le t_i\le |E_i|$$ ) for $$i=1,2,\ldots ,m$$ . A vertex coloring $$\varphi $$ is proper if the number of colors occurring in edge $$E_i$$ satisfies $$s_i\le |\varphi (E_i)|\le t_i$$ , for every $$1\le i\le m$$ . If $$s_i=s$$ and $$t_i=t$$ for all i, we simply denote the color-bounded hypergraph by $${\mathcal {H}}=(X, {\mathcal {E}},s,t)$$ . A set of positive integers $$\Phi (\mathcal {H})$$ is called feasible, if it consists of all k for which there exists a proper coloring of $$\mathcal {H}$$ using precisely k colors. Chromatic spectrum of a hypergraph $$\mathcal {H}$$ is a vector with each entry $$r_k$$ equal to the number of partitions of vertex set induced by all proper colorings using k colors. Let S be a finite set of positive integers. A color-bounded hypergraph is a one-realization of S if its feasible set is S and each entry of its chromatic spectrum is either 0 or 1. In this paper, we determine the minimum number of vertices of r-uniform color-bounded hypergraphs $${\mathcal {H}}=(X, {\mathcal {E}},2,t)$$ which are one-realizations of S for the case when $$\lceil \frac{r}{2}\rceil

For any set S of positive integers, a mixed hypergraph $${\mathcal {H}}$$ is a one-realization of S if its feasible set is S and each entry of its chromatic spectrum is either 0 or 1. In this paper, a tight lower bound on the minimum number of edges of 3-uniform bi-hypergraphs which are one-realizations of a given set S is presented. As a result, we partially solve an open problem proposed by Bujtás and Tuza in 2008. [ABSTRACT FROM AUTHOR]

Let $$S(n,k)$$ be the Stirling number of the second kind. In this paper, we prove that for any integer $$n$$ at least three, there exists a 3-uniform $$\mathcal{C}$$ -hypergraph $$\mathcal{H}$$ with chromatic spectrum $$R(\mathcal{H})=(1,r_2,S(n,3),\ldots , S(n,n))$$ , which is the minimum chromatic spectrum of 3-uniform $$\mathcal{C}$$ -hypergraphs with upper chromatic number n. [ABSTRACT FROM AUTHOR]

Polyominos was extensively studied in chemistry and mathematics. The spectrum of a (molecule) graph is the set of eigenvalues of its adjacency matrix. The spectrum and the number of spanning trees of polyominos on the torus are determined in this paper. [ABSTRACT FROM AUTHOR]

Suppose that G=( V, E) is a graph with even vertices. An even cycle C is a nice cycle of G if G− V( C) has a perfect matching. An orientation of G is a Pfaffian orientation if each nice cycle C has an odd number of edges directed in either direction of the cycle. Let P and C denote the path and the cycle on n vertices, respectively. In this paper, we characterize the Pfaffian property of Cartesian products G× P and G× C for any graph G in terms of forbidden subgraphs of G. This extends the results in (Yan and Zhang in Discrete Appl Math 154:145-157, 2006). [ABSTRACT FROM AUTHOR]

An orientation of a graph G with even number of vertices is Pfaffian if every even cycle C such 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 G has one, then the number of perfect matchings of G can 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. [ABSTRACT FROM AUTHOR]

Let G be a (molecule) graph. A perfect matching, or Kekulé structure of G is a set of independent edges covering every vertex exactly once. Enumeration of Kekulé structures of a (molecule) graph is interest in chemistry, physics and mathematics. In this paper, we focus on some polyominos on the torus and obtain the explicit expressions on the number of the Kekulé structures of them. [ABSTRACT FROM AUTHOR]

Disperse fine equiaxed α-Al2O3 nanoparticles with narrow size distribution are important materials in nanotechnology and nanomaterials, but syntheses of disperse fine equiaxed α-Al2O3 nanoparticles usually result in fine γ-Al2O3 nanoparticles or large α-Al2O3 nanoparticles larger than 15 nm. α-Al2O3 has a higher surface energy than γ-Al2O3 and becomes thermodynamically not stable with respect to γ-Al2O3 at specific surface areas larger than 100 m2/g (at sizes smaller than 15 nm for spherical particles) at room temperature. So disperse fine equiaxed α-Al2O3 nanoparticles smaller than 15 nm with narrow size distribution are extremely difficult to synthesise. Here we show the successful synthesis of disperse fine equiaxed α-Al2O3 nanoparticles with average sizes below 10 nm and narrow size distribution by selective corrosion and refined fractionated coagulation separation. An almost fully dense nanocrystalline α-Al2O3 ceramic with a relative density of 99.5% and an average grain size of 60 nm can be sintered from disperse fine equiaxed α-Al2O3 nanoparticles with narrow size distribution. [ABSTRACT FROM AUTHOR]