=Paper=
{{Paper
|id=Vol-2604/paper83
|storemode=property
|title=About φ-Transformation Graphs as a Tool for Investigations
|pdfUrl=https://ceur-ws.org/Vol-2604/paper83.pdf
|volume=Vol-2604
|authors=Volodymyr Petrenjuk
|dblpUrl=https://dblp.org/rec/conf/colins/Petrenjuk20
}}
==About φ-Transformation Graphs as a Tool for Investigations==
https://ceur-ws.org/Vol-2604/paper83.pdf
About φ-Transformation Graphs as a Tool for
Investigations
Volodymyr Petrenjuk
Tcentralukrainian national technical university, Universitetskyj 8, Kropivnytskyj, Ukraine
petrenjukvi@i.ua
Abstract. The mathematical method φ-transformation in which large structures
are regarded as a set of small and simple substructures, which may have some
common parts that can be identified and amalgamate when constructing or re-
constructing an entire structure from a finite number of substructures has
presentation here.
Keywords: Graph representations,geometrc and yopological aspects graph
theory,expander graph
1. Introduction
Let's dissolve the problem of modeling a complex system in general form and propose
a theoretical and graphical approach as a way of thinking with artificial images-
structures. In systems modeling theory, there are mathematical methods in which
large structures are regarded as a set of small and simple substructures, which may
have some common parts that can be identified when constructing or reconstructing
an entire structure from a finite number of substructures. The main object of φ-
method is creating graph (graph model) obtained as a pair of finite sets: sets of verti-
ces and sets of edges to determine the relationships between structure of vertices as
objects. The basic idea of the method φ-transformation can be interpreted as a way to
inherit a particular property of substructures throughout the structure, depending on
the properties of the connection (identification of given parts of substructures). An
example of this is the transformation of basic system programming problems into
graph theory problems, with mathematical support for their solution algorithms.
The graph model of a mathematical model of a complex system is presented in the
form of an undirected graph G without multiple edges and loops and is studied by
studying the structured properties of a graph embedded in a closed surface S of an
undirected genus (S ) ; the graph edges placed on the S will be located at least on the
projective plane or the Mobius band glued to the oriented surface and will have no
common points except the vertices of the graph G with genus γ(G) and may not be
located only on the handles. A graph G is said to be minimal over S (𝛾(𝑆) -no irreduc-
ible) if for each proper subgraph H of graph G there is an inequality 𝛾(𝐻) ≤ 𝛾(𝑆) <
𝛾(𝐺). A minimal graph over S is called a graph G that decreases 𝛾(𝐺) after the edge
Copyright © 2020 for this paper by its authors.
Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
is removed or the edge is reduced to a point. For sphere S such are K 5 and K3,3. The
following results can be used for systematic analysis of graph models.
2. Main Definitions and Results
For a graph (obtained as a -image G St n ( g 0 ) with n vertices of the star
St n ( g 0 ) amalgamate with vertices of the set X having the number of reachability
tG (X ) and characteristics G ( X ), G ( X ) , [3-4] the following inequality holds:
() (G) tG ( X ) G ( X ) G ( X ) 1 .
Was introduced a characteristic at G (X ) is a measure of the cyclic connectivity of
2-cells of set SG (X ) as opposed to G (X ) which characterizes the cyclicity of the
set SG (X ) .They can be used in the analysis of graph models of linguistic circuits
which know that vertex and vertex links have some common property-context and
some pairs of vertexes may conflict or contradict each other. To resolve these con-
flicts, we suggest placing graph models on the surface of another kind without cross-
ing the edges at the inner points. In order to investigate the behavior of a mathemati-
cal model of a complex system placed on the orienting surface S, its graph model G
without multiple edges and loops is considered. Then it is possible to use the trans-
form method created for graphs to solve modeling problems by splitting into "sim-
pler" submodels with further identification of elements made with predefined proper-
ties. So the expansion of model G can be determined by the following transformation:
n
: (G, St n ( g 0 ), (g i ai )) (,{ai }in1 )
i 1
where {ai }in1 is the set X of points of graph G with the number of reachability
tG (X ) , which is one set for identification and amalgamation, and the other {g i }in1
is the set of end vertices of the star St n ( g 0 ) with center g 0 . Generalization of the
characteristic relating to the cyclic structure of the set X points of the graph G embed-
ded in the surface S. Introduction of a new characteristic that measures the chain
structure of the set X of points of graph G on S. This result will be useful in the sys-
tematic analysis of both graph models and their topological aspect. which will have
common properties at the edges and vertices of the graph model. The solution to our
problem is based on the method of graph transformations [1-2], whose founder is
M.P. Khomenko, and the concepts he introduced. For the take of completeness, we
present the most important part of them.
Definition 1.1. A -transformation of space into X relative homeomorphism
q
: (, ) ( X , A) which is the sum 0 i of q 1 homeomorphisms:
i 1
1. 0 | \ : \ X \ A , 0 is a homeomorphism;
2. j : j Aj ;
q k 1 q
3. j | , j j | , k j 1(1)q ;
j 1 j 1 j k 1
dj dj
4. j ji ; ji | ji : ji A ji ; d j 2; j 1(1)q ;
i 1 i 1
5. 1 dim( ji ji" ) dim( j ), i i" , i, i" 1(1)q :
6. ji ij , j i, i, j 1(1)q.
An important class -transformations are -transformations satisfying the condi-
tion: j i j i at (i i ) ( j j ) . Then the subspace A is decomposed into
the sum q of the subspace systems j i homeomorphic to each other within each
system. Thus, on the subspace A , the relation R - equivalence is given, i.e.
q dj m m0
R R j , moreover R j ji ji . Let r , X Xl ,
j 1 i 1 r 1 l 1
p0 (X r ) p0 ( X l ) 1 for l 1(1)m0 , r 1(1)m .
Define -transformation : ( X, A) ( X , A) in accordance with definition 1.1.
We introduce the following characteristics -transformation:
q
k rj j j i | j i j i r i 1(1)d j , i 1(1)d j k r j k rj j ,
j1
j j
k
m
( j ) k j j k j j 0 j , j 1,2, q j j, j k j j 0 k j j 0
j j
k rj j ,
r 1
j j , j 1(1)q .
Possible causes are shown in figure 1.
.
Fig. 1. Possible causes
The set A(𝜙𝑗 ) is uniquely defined. We denote k rj by a number k rj j .
3. Main Three Graphs
Definition 3.1. The - base j ( j ) of reflection j : j A j with given -
transformation : ( , ) ( X , A) is the sum of those components of the subspace
X that intersect with the subspace j , that is j r , J j r k rj 0 .
rJ j
Definition 2.2. The complex -base Bl B( X l ) over X l is called the prototype of
this component at a given -transformation, i.e. Bl 1 ( X l ) .
Statement 2.1. If fixed -transformation : (, ) ( X , A) , J l j j Bl ,
l J l , l 1(1)m , then
1) Bl B j , l 1(1)m0 ,
j J l
2) Bl Bl , l l , l , l 1(1)m0 ,
m0
3) l q .
l 1
Proof of this statement follows from the fact that Bl - the set of components of spaces
"glued" into a component X l on the subsystem j .
Definition 2.3. The graph of the complex -base Bl - transformation
: (, ) ( X , A) is called a graph Z l , Z l ( Z l0 , Z l1 ) , where Z l0 x r r Bl
the vertices x r are joined by edges so that k rj 0 a tree with a k rj 1 -loop in x r for
all j, j 1(1)q is formed on all vertices.
Definition 2.4. The graph -base -transformation is called a graph
m0
Z , X Z l .
l 1
Statement 2.2. The graph Z , X is defined uniquely if and only if, when
p 0 ( B j ) 2 for j 1(1)q , i.e. we have no more than two connected components
that intersect with the system j . If ( j j1 j 2 ) ( d j 2) for all j 1(1)q ,
then the graph Z , X is uniquely defined.
Theorem 2.1. For each graph Z , X Z -bases -transformations
: (, ) ( X , A) we have:
1) p0 ( Z ) p0 ( X ) ;
q
2) p1 ( Z ) d j p0 ( X ) p0 ( ) q ;
j 1
In order to ensure that these properties are valid, it is sufficient to calculate
1 ( Z (, X )) , 1 ( Z ) p0 j 1 ( k rj 1) k rj k rj 0 ,
q q m q
j 1 j 1r 1 j 1
where m p0 () and use the formula p1 ( Z ) 1 ( Z ) 0 ( Z ) p0 ( Z ) .
Theorem 2.2. The graphs of the -bases Z , X are simple (i.e. without multiple
edges and loops) if and only if, when
k rj 1 and j k rj 0 k rj 0 1 ,
where r r, r, r 1(1)m, j 1(1)q . In other words, the graphs Z are simple if
and only if, when:
1) we have only one subspace j i on each component r ;
dj
2) there no more than one system j i for each pair of such components.
i 1
Definition 2.5. The graph -transformation | Bl : Bl , Bl X l , X l A
of a complex -base Bl at a given -transformation of space is called a graph
l , where
0l {x r / X r Bl } { y j / A j Bl } ,
j j
1l {(k r k r ' )( x r , y j ) /( X r Bl ) ( A j Bl )}
j j'
{( y j , y j ) /(k r k r A( j )) ( A j Bl )}
Definition 2.6. Graph -transformation of space is the graph
m
( , X ) l
l 1
Statement 2.3.
1. The arbitrary 𝜙-transform graph (, X ) is uniquely defined and is simple if
j j
and only if, when: k r k r ' 1, j 1(1)q, r 1(1)m;
2. There is a connection between p1 ( Z ) and p1 () .
Consider the following example in figures 2,3, where:
3 3 2
1 1 j , 2 2 j , 3 3 j .
j 1 j 1 j 1
1 2 3
32
12
21 22 31
11 13
23
Fig. 2. Consider the following example
Fig. 3. Consider the following example
4. -Transformations for Graphs on Some Surfaces
4.1. Projective Plane
The problem of studying the structure of all minimal non-planar projective graphs is
solved by sorting through all the different variants of removing one of the vertices of
one of the 35 minors of the projective plane and selecting non isomorphic graphs of
nonorientable genus 1. Since [5] does not show the diagrams of these graphs, the
construction of all minimal non-planar projective graphs, and in the study of the prop-
erties of these subgraphs of the minors of the projective plane relative to the number
of reachability of the set of points and the genus of graph.
The solution of this problem is to construct all minimal non-outer projective-
planar graphs by sorting out all the different variants of removing one of the vertices
of a graph - minor of a projective plane and selecting non isomorphic graphs of
nonorientable genus 1. Constructing similarly to how minimally projective non-planar
graphs K 5 or K 3,3 are formed from minimal non-outer planar graphs K 4 or K 2,3 by
gluing a simple star St(v) to the minimum power subset of points of graphs K 4 or
K 2,3 with number reachability equals 2. Main results: theorem 3.1 and diagrams of
118 non-outer projective-planar graphs are given and the numbers of reachability of
sets of vertices of minors of a projective plane and sets with points of attachment of a
star to subgraphs of these minors are calculated. The full list of thess non-outer pro-
jective-planar graphs will be published as soon as possible.
Theorem 3.1. For an arbitrary graph - obstruction G of the projective plane N1
and each of its vertices v with the set M (v) of all vertices of the incident occur the
following statements:
1. For the subgraph G \ v of the nonorientable genus, the following relations
will take place:
a) If (G \ v) 1 , then we have the following relations a1) and one of a2) or a3):
a1) tG\v (M (v), N1) 2 , wherein the set M (v) belongs to the boundaries s1, s2
of two cells s1 , s2 of the projective plane having at least one common vertex;
a2) each edge of the subgraph G \ v is significant in relation genus (G \ v) with
respect to the removing the edge or compressing it in point;
a3) each edge of a subgraph G \ v is significant with respect to the removal or
compression operations of an edge;
b) If (G \ v) 0 then, one of the following two relationships will occur:
b1) tG \ v (M (v), N1) 3 and the set M (v) is located on the boundaries of three
cells s1, s2 , s3 of the projective plane satisfying the relation s3 s1 s2 , each edge
of the subgraph G \ v being significant relative tG \ v (M (v), N1) to the operations of
removing the edge or compressing it to a point, and each point w of the set M (v)
satisfies equality tG \ v (M (v) \ {w}, N1) tG \ v (M (v), N1) 1 ;
b2) tG \ v (M (v), 0 ) 2 , where tG \ v (M (v), 0 ) is the number of reachability of
the set M (v) relative to the euclidean plane 0 , is realized by minimal embedding
f : (G \ v) 0 at the boundaries s1, s2 of the cells s1, s2 , where {s1, s2} 0 \ f (G \ v) ,
which satisfies equality s1 s2 , that is, separated by a ring from the cells, then
relative to the projective plane, the set M (v ) will have a number of reachability
tG \ v (M (v), N1) 2 , with each point w of the set M (v) satisfies equality
tG\v (M (v) \ {w}, N1 ) tG\v (M (v), N1 ) and the set f (M (v) \ {w}) by some embedding
f ': G \ v N1 is placed at the boundaries s1' , s2' of two cells s1' , s2' having at least
one common point where {s1' , s 2' } 0 \ f ' (G \ v) , and equality s1' s 2' is satis-
fied.
2. Each minor G of the nonorientable genus 2 (except G3 , E1, G4 ) is covered
by a maximum of 4 (eg, graphs A2, G1) subgraphs or parts homeomorphic to one of
the following graphs: K2,3, K4, K5 \ e, K3,3 \ e, K5, K3,3 and relatively Klein surface N2
the number of reachability 2 for the set of vertices (for G{G3 , E1 , G4 } we have),
and for each removed edge e the graph G \ e will have at N1 the number of reacha-
bility equals 2 for the set of vertices;
3. The presence of the coating specified in the statement 2 is not sufficient to
make the graph an obstruction of nonorientable genus 2.
4. If (G \ v) 0 and on the Euclidean plane 0 made up a set M (v) of points
of a graph G formed from the obstruction graph of a projective plane N 1 by removal
of a vertex v and adjacent edges is given by an arbitrary minimal embedding
f : G \ v 0 on the boundaries of two cells that have no common points and have
end points that does not belong to their borders. Removing an arbitrary point from the
set M leads to the failure of relation 4.
Fig, 4. Illustrates the relation b) of statement 1 of theorem 3.1, where sets
{1,2,4,5,8,9} for graph C4 \ 5 , {2,4,6,9} for graph E22 \ 5 .
Proof. We prove statements 1 of Theorem 3.1. Suppose that for each vertex v of the
graph - obstruction G for a projective plane N1 with the set M (v) of all vertices
incident v , there is a subgraph G \ v of a nonorientable genus (G \ v) . Then we will
either (G \ v) 1 have and G \ v contain a subgraph or part homeomorphic K5 , or
K 3,3 , or G \ v that subgraph does not contain these partial subgraph, where K5 has
two non-isomorphic embeddings in N1 and K 3,3 has one non isomorphic embedding
in N1 . Prove the relation a1) relation a) statement 1, namely (G \ v) 1 , if, then
inequality tG \ v (M (v), N1 ) 2 holds. Using the opposite method, suppose that
tG\v (M (v), N1 ) 2 , that is, the set M (v) is placed by some minimal embedding f of a
graph G \ v in N1 the boundaries of at least three cells of the projective plane, namely
s1, s2, s3 . Let the graph G be the φ-image of the graph G \ v and StG (v) , if the pairs of
vertices (v1i , v2i ) are identified, where v1i M (v) , v2i StG 0 (v) \ {v} , i 1(1) degG (v) , To con-
tinue embedding f : G \ v N1 on the graph G , it is necessary and sufficient to
attach all the edges of the star and its center to one cell formed of two cells s1, s2 ,
where {s1, s2 } N1 \ f (G \ v) whose boundaries have at least one , the common vertex w ,
where w G 0 \ {v} s1 s 2 , and contain the set M (v) . To form a single surface cell
from these cells s1, s2 , we attach on N1 a Mobius strip L on which we place
f ' ( N (w)) by new embedding , f ': G \ v N2 , where f ' ( N (w) L ,
f ' |G1 \ St1 (v) \ N ( w) f |G1 \ St1(v) \ N ( w) , N (w) is the smallest subset of the set of
adjacent edges belonging to the boundary of one or to the boundaries of several cells,
which on N1 at least one side separate the cell s1 from cells s2 , N (w) N1(w, s1, s2 )
Note that the insertion of an edge adjacent w to the Mobius strip will be to separate
some of the inner points of the edge, which it splits into two parts, and to place its
copies on diametrically opposite parts of the circle, and the edges will have endpoints
of these copies and the boundary of that edge. As a result, we get a sell s0 where
s0 s1 s2 , {s0} N 2 \ f ' (G1 \ St1(v)) in which we put vertex v the center of the
star and the subset St1 (v) of its rays of edges that terminate as a bundle of straight
segments finished on s0 . Then we will have at least one edge (v, u ) , where
u s3 \ (s1 s 2 ) there is no investment f ' (v, u) in N2 , that is (G \ (v, u)) 2 . This con-
tradicts the condition that the graph is an obstruction graph of type 2, the assumption
is incorrect. Then the assumption is wrong, we will have equality tG \ v (M (v), N1) 2 .
We prove the relation a2) of the statement 1. We give the graph G \ e as an φ-
image of the graph (G \ v) \ e and in the identification of pairs of vertices (v1i , v2i ) , where
v1i M (v) , v2i StG 0 (v) \ {v} , i 1(1) degG (v) , which satisfies the equality (G \ e) 1 ,
since the graph is an obstruction of nonorientable genus 2. Since (G \ v) \ e (G \ e) \ v and
by Theorem 1[5] (G \ e) ((G \ v) \ e) t (G \v)\e (M (v), N1 ) 1 , then we will have inequality
((G \ e) \ v) t(G \ e) \ v ( M (v), N1 ) 2 , so deleting an arbitrary edge leads either to a
decrease of 1 genus of subgraph (G \ e) \ v and then ((G \ e) \ v) 0 , or to a de-
crease in the number t (G \ e) \ v ( M (v), N1 ) of reachability by 1 and then
t(G \ e) \ v ( M (v), N1 ) 1 . The materiality of the edges of the subgraph relative to the
genus upon removal is proved. We will prove other statements similarly and present-
ed proofs as soon as possible.
4.2. Klein surface
Another problem is constructing all non-outer Klein-planar graphs. In [8] a solution to
a similar problem of constructing non-Klein surface graphs by the method of relativ-
istic components was presented.
Theorem 3.2. Each graph obstruction H for N 2 -surface of the nonorientable ge-
nus 2 satisfies the following statements:
1. An arbitrary edge u, u (a, b) is placed on the Mobius strip by some minimal
embedding of the graph H in N3 and there is a minimum on inclusion projective-
planar subgraph K of the graph or a part of it satisfying the condition:
(t K ({a, b}, N3 ) 1) (t K \ u ({a, b}, N 2 ) 2) ;
2. There is a finite smallest inclusion set of different subgraphs K i covering the
set of edges of a 2-connected graph H , where K is a local projective-planar sub-
graph or partial subgraph H \ e of a graph, homeomorphic K5 \ e or K 3,3 \ e ;
3. Every 8-vertex graph - obstruction of non-oriented genus 3 is covered by a min-
imum of 5 or a maximum of 6 subgraphs or parts of a homeomorphic planar graph
with sets of points with reachability 2, or projective-planar, or non-projective-planar
graphs (possibly without an edge) from the list of 118 non outer projective planar
graphs or set of 103 graphs - obstructions of the projective plane [4].
Fig, 4. φ- transformation of the non-outer projective planar graph E18 and
St4 (9) give non-outer Klein planar graph E44
5. Conclusions
The use of the φ-transformation of graphs method for the above problems for the
projective plane and Klein surface can be generalized to an arbitrary nonrientable
surface.
References
1. Khomenko, M.P.:Topological aspects of graph theory. Institute of Mathematics, Kiev
(1971)
2. Khomenko. M.P.: φ- transformation of graphs. Institute of Mathematics, Kiev (1973)
3. Petrenjuk, V.I., Petrenjuk, D.A., Shulenok,I.B.: Upper bound of the orientable genus of
amalgamation simple graphs, Theory optimal desigions, .69-79, Kyjv (2018)
4. Petrenjuk, V.I., Petrenjuk, D.A.: Upper bound of the nonorientable genus of amal-
gamation simple graphs. Computer mathematic 1, 10-19. Kyjv (2019)
5. Archdeacon, D., Hartsfield, N., Little, C. H. Mohar, C., B.: Obstructions sets for outer-
projective -planar graphs. Ars Combinatoria 49, 113-128; (1998)
6. Hur Surkhjin: The kuratowski covering conjecture for graphs of the order less than 10.
Dissertation, The Ohio State University (2008).
7. Bojan Mohar, Carsten Thomassen: Graphs on surfaces, Johns Hopkins University Press,
(2001)
8. Anna Flцtotto: Embeddability of graphs into the Klein surface. Dissertation, Universitаt
Bielefeldvorgeleg (2010)