We establish a new generating theorem of even triangulations of the projective plane using an operation called a Q4-reduction. That is, every even triangulation of the projective plane can be ...obtained from one of the Q4-irreducible even triangulations, which contains a special subgraph named a projective-triangular cupola (or simply PTC) as its subembedding, by a sequence of Q4-expansions. By the result, we show that the set of (P4,Q4)-irreducible even triangulations coincides with that of (P,Q)-irreducible ones on the projective plane as well as the spherical case. However, we show that the property does not hold in general for the other closed surfaces.
We shall determine exactly two (P,Q)-irreducible even triangulations of the projective plane. This result is a new generating theorem of even triangulations of the projective plane, that is, every ...even triangulation of the projective plane can be obtained from one of those two (P,Q)-irreducible even triangulations by a sequence of two expansions called a P-expansion and a Q-expansion, which were used in Batagelj (1984, 1989), Drapal and Lisonek (2010). Furthermore, we prove that for any closed surface F2 there are finitely many (P,Q)-irreducible even triangulations of F2.
Generating even triangulations on the torus Matsumoto, Naoki; Nakamoto, Atsuhiro; Yamaguchi, Tsubasa
Discrete mathematics,
July 2018, 2018-07-00, Letnik:
341, Številka:
7
Journal Article
Recenzirano
Odprti dostop
A triangulation on a surface F is a fixed embedding of a loopless graph on F with each face bounded by a cycle of length three. A triangulation is even if each vertex has even degree. We define two ...reductions for even triangulations on surfaces, called the 4-contraction and the twin-contraction. In this paper, we first determine the complete list of minimal 3-connected even triangulations on the torus with respect to these two reductions. Secondly, allowing a vertex of degree 2 and replacing the twin-contraction with another reduction, called the 2-contraction, we establish the list for all minimal even triangulations on the torus. We also describe several applications of the lists for solving problems on even triangulations.
In this paper, we prove that every 4-connected even triangulation on the sphere can be obtained from the octahedron by a sequence of two kinds of transformations called a 4-splitting and a ...twin-splitting, only through 4-connected even triangulations. As a corollary, taking a dual, we can also generate all cyclically 4-edge-connected cubic bipartite graphs on the sphere.
As a sequel of a previous paper by the authors, we present here a generating theorem for the family of triangulations of an arbitrary punctured surface with vertex degree ≥ 4. The method is based on ...a series of reversible operations termed reductions which lead to a minimal set of triangulations in such a way that all intermediate triangulations throughout the reduction process remain within the family. Besides contractible edges and octahedra, the reduction operations act on two new configurations near the surface boundary named quasi-octahedra and
-components. It is also observed that another configuration called
-component remains unaltered under any sequence of reduction operations. We show that one gets rid of
-components by flipping appropriate edges.
We define two reductions a 4-contradiction and a 2-removal for even triangulation on a surface. It is well known that these reductions preserve some properties of graphs. The complete lists of ...minimal even triangulations for the sphere, the projective plane and the torus with respect to these reductions have been already determined. In this paper, we make the complete list of minimal even triangulations of the Klein bottle and prove some applications by checking the list.
In 1995, Smarandache talked for the first time about neutrosophy and he defined one of the most important new mathematical tool which is a neutrosophic set theory as a new mathematical tool for ...handling problems involving imprecise, indeterminacy, and inconsistent data. He also defined the neutrosophic norm and conorms namely N-norm and N-conorm respectively. In this paper we give generating theorems for N-norm and N-conorm. Given an N-norm we can generate a class of N-norms and N-cnorms, and given an N-conorm we can generate a class of N-conorms and N-norms. We also give bijective generating theorems for N-norms and N-conorms. Keywords: N-norm; N-conorm; generating theorem; bijective generating theorem.
Generating bricks Norine, Serguei; Thomas, Robin
Journal of combinatorial theory. Series B,
09/2007, Letnik:
97, Številka:
5
Journal Article
Recenzirano
Odprti dostop
A brick is a 3-connected graph such that the graph obtained from it by deleting any two distinct vertices has a perfect matching. The importance of bricks stems from the fact that they are building ...blocks of the matching decomposition procedure of Kotzig, and Lovász and Plummer. We prove a “splitter theorem” for bricks. More precisely, we show that if a brick
H is a “matching minor” of a brick
G, then, except for a few well-described exceptions, a graph isomorphic to
H can be obtained from
G by repeatedly applying a certain operation in such a way that all the intermediate graphs are bricks and have no parallel edges. The operation is as follows: first delete an edge, and for every vertex of degree two that results contract both edges incident with it. This strengthens a recent result of de Carvalho, Lucchesi and Murty.
Let
be the class of all
k
-edge connected 4-regular graphs with girth of at least
g
. For several choices of
k
and
g
, we determine a set
of graph operations, for which, if
G
and
H
are graphs in
,
G
...≠
H
, and
G
contains
H
as an immersion, then some operation in
can be applied to
G
to result in a smaller graph
G
′ in
such that, on one hand,
G
′ is immersed in
G
, and on the other hand,
G
′ contains
H
as an immersion.
PDF
