Search

The complete forcing number of a graph G is the cardinality of a minimum subset of E(G) to which the restriction of every perfect matching M is a forcing set of M. In a previous paper (He et al., J Math Chem 59:1767–1784, 2021), we presented a complete forcing set of a hexagonal system in terms of elementary edge-cut cover, and a lower bound for the complete forcing number of a normal hexagonal system by matching numbers of some subgraphs of its inner dual graph. In this paper, we show that the complete forcing number of a normal hexagonal system without 2 × 3 subsystems attains the above lower bound. As an example, we present an expression of the complete forcing numbers of pyrene systems. Besides, for a parallelogram hexagonal system, we obtain that its complete forcing number is larger than the lower bound by at most 1. [ABSTRACT FROM AUTHOR]

Henning et al. (Discrete Appl Math 162:399–403, 2014) proved that if G is a bipartite, cubic graph of order n and of girth at least 6, then i (G) ≤ 4 11 n . In this paper, we improve the 4 11 -bound to a 5 14 -bound, and prove that if G is a bipartite, cubic graph of order n and of girth at least 6, then i (G) ≤ 5 14 n . [ABSTRACT FROM AUTHOR]

Graphs considered in this paper are finite, undirected and without loops, but with multiple edges. For an integer t ≥ 1 , denote by MG t the class of graphs whose maximum multiplicity is at most t. A graph G is called strictly t-degenerate if every non-empty subgraph H of G contains a vertex v whose degree in H is at most t - 1 . The point partition number χ t (G) of G is the smallest number of colors needed to color the vertices of G so that each vertex receives a color and vertices with the same color induce a strictly t-degenerate subgraph of G. So χ 1 is the chromatic number, and χ 2 is known as the point aboricity. The point partition number χ t with t ≥ 1 was introduced by Lick and White (Can J Math 22:1082–1096, 1970). If H is a simple graph, then tH denotes the graph obtained from H by replacing each edge of H by t parallel edges. Then ω t (G) is the largest integer n such that G contains a t K n as a subgraph. Let G be a graph belonging to MG t . Then ω t (G) ≤ χ t (G) and we say that G is χ t -perfect if every induced subgraph H of G satisfies ω t (H) = χ t (H) . Based on the Strong Perfect Graph Theorem due to Chudnowsky, Robertson, Seymour and Thomas (Ann Math 164:51–229, 2006), we give a characterization of χ t -perfect graphs of MG t by a set of forbidden induced subgraphs (see Theorems 2 and 3). We also discuss some complexity problems for the class of χ t -critical graphs. [ABSTRACT FROM AUTHOR]

Let R be a commutative ring with 1. In Biswas et al. (Disc Math Algorithms Appl 11(1):1950013, 2019), we introduced a graph G(R) whose vertices are elements of R and two distinct vertices a, b are adjacent if and only if a R + b R = e R for some nonzero idempotent e in R. Let G ′ (R) be the subgraph of G(R) generated by the non-units of R. In this paper, we characterize those rings R for which the graph G ′ (R) is connected and Eulerian. Also we characterize those rings R for which genus of the graph G ′ (R) is ≤ 2 . Finally, we show that the graph G ′ (R) is a line graph of some graph if and only if R is either a regular ring or a local ring. [ABSTRACT FROM AUTHOR]

In the last few decades there has been a revival of interest in diagrams in mathematics. But the revival, at least at its origin, has been motivated by adherence to the view that the method of mathematics is the axiomatic method, and specifically by the attempt to fit diagrams into the axiomatic method, translating particular diagrams into statements and inference rules of a formal system. This approach does not deal with diagrams qua diagrams, and is incapable of accounting for the role diagrams play as means of discovery and understanding. Alternatively, this paper purports to show that the view that the method of mathematics is the analytic method is capable of dealing with diagrams qua diagrams, and of accounting for such role. [ABSTRACT FROM AUTHOR]