Let be the greatest odd integer less than or equal to . In this paper we provide explicit formulae to compute -graded Betti numbers of the circulant graphs . We do this by showing that this graph is the product (or join) of the cycle by itself, and computing Betti numbers of . We also discuss whether such a graph (more generally, ) is well-covered, Cohen-Macaulay, sequentially Cohen-Macaulay, Buchsbaum, or .
Using results of Altshuler and Negami, we present a classification of biembeddings of symmetric configurations of triples in the torus or Klein bottle. We also give an alternative proof of the structure of 3-homogeneous Latin trades.
The following result is proved: if a bipartite graph is not a circle graph, then its complement is not a circle graph. The proof uses Naji’s characterization of circle graphs by means of a linear system of equations with unknowns in .At the end of this short note I briefly recall the work of François Jaeger on circle graphs.
Let be a weighted hypergraph with edges of size at most 2. Bollobás and Scott conjectured that admits a bipartition such that each vertex class meets edges of total weight at least , where is the total weight of edges of size and is the maximum weight of an edge of size 1. In this paper, for positive integer weighted hypergraph (i.e., multi-hypergraph), we show that there exists a bipartition of such that each vertex class meets edges of total weight at least , where is the number...
An additive hereditary graph property is any class of simple graphs, which is closed under isomorphisms unions and taking subgraphs. Let denote a class of all such properties. In the paper, we consider H-reducible over properties with H being a fixed graph. The finiteness of the sets of all minimal forbidden graphs is analyzed for such properties.
In this paper, we present characterizations of pairs of graphs whose join graphs are 2-minimally nonouterplanar. In addition, we present a characterization of pairs of graphs whose join graphs are 2-minimally nonouterplanar in terms of forbidden subgraphs.
The purpose of this paper is to give characterizations of graphs whose vertex-semientire graphs and edge-semientire graphs have crossing number 2. In addition, we establish necessary and sufficient conditions in terms of forbidden subgraphs for vertex-semientire graphs and edge-semientire graphs to have crossing number 2.
Let G be an edge-colored connected graph. A path P is a proper path in G if no two adjacent edges of P are colored the same. If P is a proper u − v path of length d(u, v), then P is a proper u − v geodesic. An edge coloring c is a proper-path coloring of a connected graph G if every pair u, v of distinct vertices of G are connected by a proper u − v path in G, and c is a strong proper-path coloring if every two vertices u and v are connected by a proper u− v geodesic in G. The minimum number of...
In this paper we present characterizations of graphs whose plick graphs are planar, outerplanar and minimally nonouterplanar.
The infimum of the least eigenvalues of all finite induced subgraphs of an infinite graph is defined to be its least eigenvalue. In [P.J. Cameron, J.M. Goethals, J.J. Seidel and E.E. Shult, Line graphs, root systems, and elliptic geometry, J. Algebra 43 (1976) 305-327], the class of all finite graphs whose least eigenvalues ≥ −2 has been classified: (1) If a (finite) graph is connected and its least eigenvalue is at least −2, then either it is a generalized line graph or it is represented by the...