Science and Technology Indonesia e-ISSN:2580-4391 p-ISSN:2580-4405 Vol.
No.
July 2022 Research Paper Enumerate the Number of Vertices Labeled Connected Graph of Order Seven Containing No Parallel Edges Muslim Ansori1 .
Wamiliana1 *.
Fitriani1 .
Yudi Antoni1 .
Desiana Putri1 1 Department of Mathematics.
Faculty of Mathematics and Natural Science.
Universitas Lampung.
Bandarlampung, 35145.
Indonesia *Corresponding author: wamiliana.
1963@fmipa.
Abstract A graph that is connected G(V,E) is a graph in which there is at least one path connecting every two vertices in G.
otherwise, it is called a disconnected graph.
Labels or values can be assigned to the vertices or edges of a graph.
A vertex-labeled graph is one in which only the vertices are labeled, and an edges-labeled graph is one in which only edges are assigned values or labels.
If both vertices and edges are labeled, the graph is referred to as total labeling.
If given n vertices and m edges, numerous graphs can be made, either connected or disconnected.
This study will be discussed the number of disconnected vertices labeled graphs of order seven containing no parallel edges and may contain loops.
The results show that number of vertices labeled connected graph of order .
Oe.
Oe.
) seven with no parallel edges is N(G7,m, g ) l = 6,727yCm while for 7 O g O 21.
N(G7,m, g ) l = k g C gOe1 , where k7 =30,160, k8 = 30,765, k9 =21,000, k10 =28,364, k11 = 26,880, k12 =26,460 , k13 = 20,790, k14 =10,290, k15 = 8,022, k16 = 2,940, k17 =4,417, k18 = 2,835, k19 = 210, k20 = 21, k21 = 1.
Keywords Vertex Labeled.
Connected Graph.
Order Seven.
Loops Received: 5 April 2022.
Accepted: 13 July 2022 https://doi.
org/10.
26554/sti.
INTRODUCTION
Without any doubt, one of the most widely used fields of mathematics is graph theory, especially to represent a real-life problem because of the flexibility of drawing a graph.
The date of birth of graph theory began with the publication of EulerAos solution regarding the Konigsberg problem in 1736, one of the mathematical fields with specific birth date is graph theory (Vasudev, 2.
Given a set V=.
1 , v2 .
A A A , vn } of vertices/nodes.
VOOI, and a set of edges E=.
i j .
,jyun V}, a graph G(V,E) is a structure that consists of ordered pair of V and E.
In real-life problems, the cities, buildings, airports, and others can be portrayed by vertices, while the roads that connect the cities, the pipes that connect the buildings, the flight paths that connect the airports, and others can be portrayed by edges.
In order to represent real-life problems, on the edges, we can assign nonstructural information such as distance, time, flow, cost, and others by setting a non-negative number ci j Ou0.
There is a lot of application of graph theory in real-life problems, such as in computer science, chemistry, biology, sociology, agriculture, and others.
In computer science, the graph structure plays an important role, for example, in designing a database, software engineering, and network system (Singh.
The database is used for interconnecting analysis, as a storage system with index-free adjacency, as a tool for graphlike-query, and for other purposes.
In network design, graphbased representation makes the problem easier to visualize and provides a more accurate definition.
In agriculture, the dynamic closures of the accounting structure are represented by a directed graph .
Alvarez and Ehnts, 2.
The structure of graphs, together with discrete mathematics, are applied in chemistry to model the biological and physical properties of chemical compounds (Burch, 2.
The theoretical graph concept also was used by Gramatica et al.
to represent or describe the possible modes of action of a given pharmacological compound.
In biology, a phylogenetic tree was represented by a leaf-labeled tree (Huson and Bryant, 2006.
Brandes and Cornelsen, 2.
, while Mathur and Adlakha .
represented DNA using a combined tree.
Hsu and Lin .
presented many graph theoretical concepts in engineering and computer science, and Al Etaiwi .
used the concepts of a complete graph, cycle graph, and minimum spanning tree to generate a complex cipher text.
Priyadarsini .
explored the use of graph theory concepts, expander, and extremal graphs, in the design of some ciphers, whereas Ni et al.
created ciphers using corona and bipartite In agriculture, graph theory concepts were used to Ansori et.
group agricultural workers performing manual tasks (Kawakura and Shibasaki, 2.
, while the concept of graph coloring to optimize a farmerAos goal was used by Kannimuthu et al.
The relationship and unification of graph theory and physicalchemical measures .
uch as boiling and melting point, covalent and ionic potentials, and electronic densit.
make molecular topology can describe molecular structure comprehensively.
weighted directed graph, connectivity matrix, and DijkstraAos algorithm were used by Holmes et al.
in plasma chemical reaction engineering.
The basic structure of a directed graph is mostly used for the visualization of the reactions.
Moreover, they use Gelphi, an open-source graph software for visualization.
In 1874.
Cayley counted the number of hydrocarbon isomers Cn H2n 2 (Cayley, 1.
, and this process is similar to enumerating the number of a binary tree.
Bona .
discussed the method of enumerating trees and forests.
Redfield and Pylya are two other mathematicians that worked independently with graphical enumeration, especially in graph coloring (Bogart, 2.
, and in graph enumeration, a comprehensive explanation of PylyaAos counting theorem is one of the most powerful tools.
The number of graphs that can be formed for labeled and unlabeled graphs is different if we are given n vertices and m For example, given n= 3 and m= 2, the number of simple connected unlabeled graphs that can be constructed is only one, while if every vertex is assigned labeled.
The maximum number of graphs that can be created is three.
The higher the order of the graph, the more labeled graph are formed.
Agnarsson and Greenlaw .
gave the formula to enumerate However, no formula for enumerating graphs with special properties such as planarity or connectivity was provided.
There are some studies that have been done concerning the enumeration of the vertex-labeled graph with connectivity In 2017.
Amanto et al.
proposed the formula to count disconnected vertices labeled graphs of order maximal four.
For order five, the number of labeled vertices in connected graphs with no loops and may contain maximal five parallel edges had been proposed by Wamiliana et al.
Amanto et al.
studied the relationship between the formula for the number of connected vertex labels with no loops in graphs of order five and order six.
Wamiliana et al.
also discussed the number of vertices labeled connected graphs of order six with no parallel edges and a maximum of ten loops, while Puri et al.
gave the formula to compute the number of vertices labeled connected graphs of order six without loops, while Ansori et al.
proposed the number of vertices labeled connected graphs of order seven with no The article is organized as follows: Section I provides information about graphs, graph applications in various fields, and previous research related to this topic.
Section II discusses Observation and Investigation, while Section i discusses Results and Discussion.
Section IV contains the conclusion.
A 2022 The Authors.
Science and Technology Indonesia, 7 .
OBSERVATION AND INVESTIGATION
Suppose that we are given the number of vertices n= 7, and the number of edges m.
We will construct connected graphs G(V,E) of order n.
Since the graph must be connected, then mOu6.
Moreover, every vertex is labeled.
Let g as the number of non-loop edges, gOunAe1.
We start firstly by constructing all basic patterns of connected graphs of order seven.
Note that the basic patterns contain no loops.
The basic pattern starts with m= 6, and with n= 7, m= 6, and constructs all possible patterns.
After all possible patterns for m= 6 are already constructed, then we continue with m= 7, and so on until m= 21.
When m= 21, only one pattern can be constructed because parallel edges are not allowed.
Figure 1 shows some examples of patterns for m= 6.
Figure 2 shows some patterns that are isomorphic with the first graph in the second row of the graphs in Figure 1, and Figure 3 shows when m= 21.
Figure 1.
Some Basic Patterns for n= 7 and m= 6 Note that all isomorphic graphs will be counted in the pattern.
However, we do not need to construct isomorphic graphs.
Figure 2 shows the patterns of isomorphic graphs of the pattern of the first graph in the second row of Figure 1.
Figure 2.
Some Patterns are Isomorphic with the First Graph in the Second Row in Figure 1 Figure 3.
The Basic Pattern for n= 7 and m= 21 Page 393 of 399 Science and Technology Indonesia, 7 .
392-399 Ansori et.
Table 1.
The Pattern for n= 7, m= 6, and g= 6 The patterns The number of isomorphic graphs C71 .
C66 = 7
2 = 2,520
Figure 4.
The Procedure C71 .
C63 .
C32 = 420
After constructing the basic pattern, the enumeration step It begins from the first pattern of n= 7 dan m= 6 by adding one loop so that m= 7, calculating the number of graphs that are able to be formed, and then continuing with this pattern by increasing the number of loops .
= .
, and so on.
Continue with this similar manner until the last pattern.
The procedure can be put in the following diagram:
C71 .
C62 .
C43 .
1= 420
RESULTS AND DISCUSSION
The first step, as given in Figure 4 is constructing all possible Because there are many patterns obtained and due to limitation of space, here we give some patterns and also the number of all possible graphs formed according to the patterns.
The obtained graphs are grouped by m and g, for example, for n=6, m= 6, and g= 6, the patterns are:
The results for all patterns are shown in Table 1 below:
Please note that in the table the dash sign (O.
means there is impossible to construct the graph, while the empty space on the table means that we are not calculate more because g is fixed in each column, adding more edges simply adds more loops, and the constructed graph already constitute a sequence of numbers.
The number in each column is able to be written as multiplication of a fix number and a sequence of number so that Table 2 can be rewritten in Table 3 as follow:
From Table 3 we can see that for every g= 6, 7.
A A A , 21, the number of graphs obtained are bigger as m increases, and the number of graphs obtained are multiplication of a fix number.
For example, for g= 6, the fix number is 6,727, and the number of graphs increases follows a certain pattens of sequence which is 1, 7, 28, 84, 210, 462, 924, 1,716, 3,003, 5,005.
28 84 210 462 924 1716 3003 5005
21 56 126 252 462 792 1287 2002
15 35 70 126 210 330 495 715
A 2022 The Authors.
C71 .
C63 .
3!= 840
C71 .
C61 .
C52 .
C33 = 420
C71 .
C61 .
C51 .
C44 = 210
C72 .
C51 .
C42 .
2!= 1,260
C72 .
C51 .
C42 .
C22 = 630
Total
6,727
Page 394 of 399 Science and Technology Indonesia, 7 .
392-399 Ansori et.
Table 2.
The Number of Vertices Labeled Connected Graph of Order Seven Containing No Parallel Edges The number of vertices labeled connected order seven graphs with no parallel edges A 2022 The Authors.
6,727
47,089
188,356
565,068
1,412,670
3,107,874
6,215,748
11,543,532
20,201,181
33,668,635
30,160
211,120
844,480
2,533,440
6,333,600
13,933,920
27,867,840
51,754,560
90,570,480
150,950,800
30,765
215,355
861,420
2,584,260
6,460,650
14,213,430
28,426,860
52,792,740
92,387,295
153,978,825
21,000
147,000
588,000
1,764,000
4,410,000
9,702,000
19,404,000
36,036,000
63,063,000
105,105,000
28,364
198,548
794,192
2,382,576
5,956,440
13,104,168
26,208,336
48,672,624
85,177,092
141,961,820
26,880
188,160
752,640
2,257,920
5,644,800
12,418,560
24,837,120
46,126,080
80,720,640
134,534,400
The number of vertices labeled connected order seven graphs with no parallel edges 26,460 185,220 740,880 2,222,640 5,556,600 12,224,520 24,449,040 45,405,360 79,459,380 132,432,300 The number of vertices labeled connected order seven graphs with no parallel edges 4,417 30,919 123,676 371,028 927,570 2,040,654 4,081,308 7,579,572 13,264,251 22,107,085 20,790 145,530 582,120 1,746,360 4,365,900 9,604,980 19,209,960 35,675,640 62,432,370 104,053,950 2,835 19,845 79,380 238,140 595,350 1,309,770 2,619,540 4,864,860 8,513,505 14,189,175
10,290
72,030
288,120
864,360
2,160,900
4,753,980
9,507,960
17,657,640
30,900,870
51,501,450
1,470
5,880
17,640
44,100
97,020
194,040
360,360
630,630
1,051,050
8,022
56,154
224,616
673,848
1,684,620
3,706,164
7,412,328
13,765,752
24,090,066
40,150,110
1,764
4,410
97,02
19,404
36,036
63,063
105,105
2,940
20,580
82,320
246,960
617,400
1,358,280
2,716,560
5,045,040
8,828,820
14,714,700
1,716
3,003
5,005
Page 395 of 399 Science and Technology Indonesia, 7 .
392-399 Ansori et.
Table 3.
Alternative form of Table 2 The number of vertices labeled connected order seven graphs with no parallel edges 1x6,727 7x6,727 28x6,727 84x6,727 210x6,727 462x6,727 924x6,727 1,716x6,727 3,003x6,727 5,005x6,727 Oe Oe Oe Oe Oe A 2022 The Authors.
Oe 1x30,160 7x30,160 28x30,160 84x30,160 210x30,160 462x30,160 924x30,160 1,716x30,160 3,003x30,160 5,005x30,160 Oe Oe Oe Oe Oe Oe 1x30,765 7x30,765 28x30,765 84x30,765 210x30,765 462x30,765 924x30,765 1,716x30,765 3,003x30,765 5,005x30,765 Oe Oe Oe Oe Oe Oe 1x21,000 7x21,000 28x21,000 84x21,000 210x21,000 462x21,000 924x21,000 1,716x21,000 3,003x21,000 5,005x21,000 Oe Oe Oe Oe Oe Oe 1x28,364 7x28,364 28x28,364 84x28,364 210x28,364 462x28,364 924x28,364 1,716x28,364 3,003x28,364 5,005x28,364 Oe Oe Oe Oe Oe Oe 1x26,880 7x26,880 28x26,880 84x26,880 210x26,880 462x26,880 924x26,880 1,716x26,880 3,003x26,880 5,005x26,880 The number of vertices labeled connected order seven graphs with no parallel edges 1x26,460 7x26,460 28x26,460 84x26,460 210x26,460 462x26,460 924x26,460 1,716x26,460 3,003x26,460 5,005x26,460 Oe Oe Oe Oe The number of vertices labeled connected order seven graphs with no parallel edges 1x4,417 7x4,417 28x4,417 84x4,417 210x4,417 462x4,417 924x4,417 1,716x4,417 3,003x4,417 5,005x4,417 Oe Oe Oe Oe Oe 1x20,790 7x20,790 28x20,790 84x20,790 210x20,790 462x20,790 924x20,790 1,716x20,790 3,003x20,790 5,005x20,790 Oe Oe Oe Oe 1x2,835 7x2,835 28x2,835 84x2,835 210x2,835 462x2,835 924x2,835 1,716x2,835 3,003x2,835 5,005x2,835 Oe Oe Oe Oe Oe 1x10,290 7x10,290 18x10,290 84x10,290 210x10,290 462x10,290 924x10,290 1,716x10,290 3,003x10,290 5,005x10,290 Oe Oe Oe Oe 1,716x210 3,003x210 5,005x210 Oe Oe Oe Oe Oe 7x8,022 28x8,022 84x8,022 210x8,022 462x8,022 924x8,022 1,716x8,022 3,003x8,022 5,005x8,022 Oe Oe Oe Oe 1,716x21 3,003x21 5,005x21 Oe Oe Oe Oe Oe 1x2,940 7x2,940 28x2,940 84x2,940 210x2,940 462x2,940 924x2,940 1,716x2,940 3,003x2,940 5,005x2,940 Oe Oe Oe Oe 1,716x1 3,003x1 5,005x1 Page 396 of 399 Science and Technology Indonesia, 7 .
392-399 Ansori et.
polynomial related to the sequence of numbers is the same.
However, because the multipliers are different, it will cause different formulas.
Result 2: Given mOu7, g= 7, the total number of vertices labeled connected graphs of order seven with no parallel edges is N(G7,m, g ) l = 30,160yC6.
Oe.
Proof:
The polynomial that represents the sequence is the same which 35 56 84 120 165 220
15 21 28 36 45 55
6 7 8 9 10
1 1 1 1
Notate N(G7,m, g ) l as the number of vertices labeled connected graphs of order seven containing no parallel edges .
oops are allowabl.
with the number of edges is m and the number of non loop edges is g.
Result 1: Given mOu6, g= 6, the total number of vertices labeled connected graphs of order seven with no parallel edges is N(G7,m, g ) l = 6,727yCm Proof:
Consider the above sequence of numbers.
That sequence of numbers is able to be represented by polynomial of order six because the fixed Q5 m = yu 6 m 6 yu 5 m 5 yu 4 m 4 yu 3 m 3 yu 2 m 2 yu 1 m yu 0 However, for m= 7, the numbers of graphs are different.
The following system of equations is obtained by substituting m= 7, 8, 9, 10, 11, 12, 13 to the equation.
Q5 m = yu 6 m yu 5 m yu 4 m yu 3 m yu 2 m yu 1 m yu 0 The following system of equations is obtained by substituting m= 6, 7, 8, 9, 10, 11, 12 to Q5 .
6, 727 = 46, 656yu6 7, 776yu5 1, 296yu4 216yu3 36yu2 6yu1 yu0
47, 089 = 117, 649yu6 16, 807yu5 2, 401yu4 343yu3 49yu2 7yu1 yu0
188, 356 = 262, 144yu6 32, 768yu5 4, 096yu4 512yu3 64yu2 8yu1 yu0
565, 068 = 531, 441yu6 59, 049yu5 6, 561yu4 729yu3 81yu2 9yu1 yu0
3, 107, 874 = 1, 771, 561yu6 161, 051yu5 14, 641yu4 1, 331yu3 121yu2 11yu1 yu0
6, 215, 748 = 2, 985, 984yu6 248, 832yu5 20, 736yu4 1, 728yu3 144yu2 12yu1 yu0
7, 776
16, 807
32, 768
59, 049
100, 000
161, 051
248, 832
1, 296
2, 401
4, 096
6, 561
10, 000
14, 641
20, 736
1, 000
1, 331
1, 728
6, 727
47, 089
188, 356
= 565, 068
1, 412, 670
3, 107, 874
6, 215, 748
By solving this system of equations we get: yu6 = 6,727 , yu5 = 57,175 151,575 1,843,198 Oe 100,905 yu yu1 = Oe 807,240 yu Thus Q5 .
=yu6 m6 yu5 m5 yu4 m4 yu3 m3 yu2 m2 yu1 m yu0
6, 727 6 100, 905 5 57, 175 4 151, 575 3
m Oe
m Oe
1, 843, 198 2 807, 240
m Oe
6, 727 6
Oe 15m5 85m4 Oe 225m 3 274m 2 Oe 120.
6, 727.
Oe .
Oe .
Oe .
Oe .
Oe .
Oe .
! 1.
Oe .
! =6, 727 y C6m Please note that for every g .
very column, the sequence of numbers is the same, except the multiplie.
Thus, the A 2022 The Authors.
844, 480 = 531, 441yu6 59, 049yu5 6, 561yu4 729yu3 81yu2 9yu1 yu0
2, 533, 440 = 1, 000, 000yu6 100, 000yu5 10, 000yu4 1, 000yu3 100yu2 10yu1 yu0
6, 333, 600 = 1, 771, 561yu6 161, 051yu5 14, 641yu4 1, 331yu3 121yu2 11yu1 yu0
13, 933, 920 = 2, 985, 984yu6 248, 832yu5 20, 736yu4 1, 728yu3 144yu2 12yu1 yu0
27, 867, 840 = 4, 826, 809yu6 371, 293yu5 28, 561yu4 2, 197yu3 169yu2 13yu1 yu0
117, 649
262, 144
531, 441
1, 000, 000
1, 771, 561
2, 985, 984
4, 826, 809
16, 80
32, 768
59, 049
100, 000
161, 051
248, 832
371, 293
10, 000
14, 641
20, 736
28, 561
30, 160
211, 120
= 2, 533, 440
6, 333, 600
13, 933, 920
27, 867, 840
, yu5 = By solving this system of equations we get: yu6 = 30,160 633,360 5,278,000 22,167,600 48,979,840 Oe 720 , yu4 = 720 , yu3 = Oe 720 , yu2 = 21,715,200 yu yu1 = Oe 53,202,240 These equations form a system of equations that can be transformed into a matrix Ax= b as follow:
46, 656
117, 649
262, 144
531, 441
1, 000, 000
1, 771, 561
2, 985, 984
These equations form a system of equations that can be transformed into a matrix Ax= b as follow:
1, 412, 670 = 1, 000, 000yu6 100, 000yu5 10, 000yu4 1, 000yu3 100yu2 10yu1 yu0 30, 160 = 117, 649yu6 16, 807yu5 2, 401yu4 343yu3 49yu2 7yu1 yu0 211, 120 = 262, 144yu6 32, 768yu5 4, 096yu4 512yu3 64yu2 8yu1 yu0 Thus Q5 .
=yu6 m 6 yu5 m5 yu4 m4 yu3 m 3 yu2 m 2 yu1 m yu0
30, 160 6 633, 360 5 5, 278, 000 4 22, 167, 600 3
m Oe
m Oe
21, 715, 200
48, 979, 840 2 53, 202, 240
m Oe
30, 160 6
Oe 21m 5 175m 4 Oe 735m 3 624m2 Oe 1764m .
30, 160 .
Oe .
Oe .
Oe .
Oe .
Oe .
Oe .
30, 160.
Oe .
Oe .
Oe .
Oe .
Oe .
Oe .
Oe .
! 1.
Oe .
! .
Oe.
=30, 160 y C6 The following results are obtained by doing the similar manner:
For mOu8, g=8, is N(G7,m, g ) l = 30,765yC7.
Oe.
For mOu9, g=9, is N(G7,m, g ) l = 21,000yC8.
Oe.
For mOu10, g=10, is N(G7,m, g ) l = 28,364yC9.
Oe.
Oe.
For mOu11, g=11, is N(G7,m, g ) l = 26,880yC10 .
Oe.
For mOu12, g=12, is N(G7,m, g ) l = 26,460yC11 .
Oe.
For mOu13, g=13, is N(G7,m, g ) l = 20,790yC12 .
Oe.
For mOu14, g=14, is N(G7,m, g ) l = 10,290yC13 Page 397 of 399 Science and Technology Indonesia, 7 .
392-399 Ansori et.
Oe.
For mOu15, g=15, is N(G7,m, g ) l = 8,022yC14 .
Oe.
For mOu16, g=16, is N(G7,m, g ) l = 2,940yC15 .
Oe.
For mOu17, g=17, is N(G7,m, g ) l = 4,417yC16 .
Oe.
For mOu18, g=18, is N(G7,m, g ) l = 2,835yC17 .
Oe.
For mOu19, g=19, is N(G7,m, g ) l = 210yC18 .
Oe.
For mOu20, g=20, is N(G7,m, g ) l = 21yC19 .
Oe.
For mOu21, g=21, is N(G7,m, g ) l = C20 Note that the multiplier for g= 6 is the same as the multiplier of t= 6 in Ansori et al.
, as well as g=7 with t= 7, and so on until g=21 with t=21.
However, the formulas are different because in Ansori et al.
the formula are for connected vertex labeled graph without loops while in this study is for connected vertices labeled graph without parallel edges.
For example, for g=8.
N(G7,m, g ) l = 30,765yC7.
Oe.
, while in Ansori et al.
, for t= 8.
N(G7,m,8 ) = 30,765yC7.
Oe.
CONCLUSIONS
Based on the above reasoning, we may conclude that the number of vertices in a labeled connected graph of order seven with no parallel edges is N(G7,m, g ) l = 6,727yCm for g= 6, while for .
Oe.
Oe.
) 7OgO 21.
N(G7,m, g ) l = k g C gOe1 , where k7 =30,160, k8 = 30,765, k9 =21,000, k10 =28,364, k11 = 26,880, k12 =26,460 , k13 = 20,790, k14 =10,290, k15 = 8,022, k16 = 2,940, k17 =4,417, k18 = 2,835, k19 = 210, k20 = 21, k21 = 1.
ACKNOWLEDGMENT
The Research Center Universitas Lampung funded this study under Postgraduate research grant project No.
815/UN26.
21/PN/2022, and the authors gratefully acknowledge the funding.
REFERENCES