Decomposition of Complete Multigraph into Wheel Graphs for Cyclic
Triple System
KHALED AHMAD MATARNEH1, MOWAFAQ OMAR AL-QADRI2,
ABDALLAH AL-HUSBAN3, RAJA'I ALDIABAT4, SHAMESEDDIN ALSHORM5*
1Faculty of Computer Studies,
Arab Open University (AOU),
Riyadh,
KINGDOM OF SAUDI ARABIA
2Department of Mathematics,
Jerash University,
Jerash,
JORDAN
3Department of Mathematics,
Faculty of Science and Technology,
Irbid National University,
JORDAN
4Department of Mathematics and Sciences,
Prince Sultan University,
Riyadh 11586,
KINGDOM OF SAUDI ARABIA
5Department of Mathematics,
Al Zaytoonah, University of Jordan,
Amman 11733,
JORDAN
Abstract: - Let be positive integer and be a wheel graph of order . In this paper, we construct a new
decomposition of into wheel graphs for . Then, new cyclic triple system will be defined to
arrange triples satisfying certain criteria. In this development, the decomposition of will be
used to construct a cyclic -fold triple system of order .
Key-Words: - Cyclic triple factorization, graph decomposition, near-four-factor, fuzzy set theory, group theory,
graph theory.
Received: March 24, 2023. Revised: November 16, 2023. Accepted: December 6, 2023. Published: December 28, 2023.
1 Introduction
A Throughout of this paper, all graphs and multisets
considered have vertices in . Let be a graph of
order , a near--factor of is a spanning subgraph
in which all vertices have a degree with exception
of one vertex (isolated vertex) which has a degree
zero. An analysis of graph G involves a list of
subgraphs in which the edge sets
split the edge set of as a whole. Another name for
it is a -design. A subgraph is called a
design if every subgraph in is
isomorphic to a predefined subgraph .
Let be a group of permutation on
leaving the multiset of subgraphs invariant. If
there is a permutation of order , then
-design is called a cyclic. Thus, the
permutation can be represented by
.
A complete multigraph is a graph where
any two vertices are joined by distinct edges. The
fundamental theorem for the existence of -
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2023.22.104
Khaled Ahmad Matarneh, Mowafaq Omar Al-Qadri,
Abdallah Al-Husban, Raja'i Aldiabat,
Shameseddin Alshorm
E-ISSN: 2224-2880
950
Volume 22, 2023
design has been stated by, [1]. There have been
several research papers relating to decomposing of
complete multigraph into different subgraphs.
For example, into crowns, [2], paths, [3] or cycles,
[4].
Furthermore, -design is known as a
balanced incomplete block design denoted by
-. On other words, - is a
pair where is a finite set of points and
is a list of -subsets (called blocks) of such that
each pair of distinct points of is contained in
precisely blocks. A -fold triple system of order ,
denoted by , is -.
The,, is called cyclic triple system,
, if then
is also in . The ensemble
of triplets generating all triplets within
through the addition of one modulo is termed
starter triplets.
The orbit of triple , represented by , is
the set that contains all unique triples in the
collection where is a triple.
The length of the orbit, written as , is
the cardinality of this orbit, represented as ,
the smallest positive integer, denoted by in this
case, for which . is said to be
precisely defined if its orbit matches ; if not, it is
deemed short. There is no block's short orbit when
is not equivalent to [5].
The existence of is an interesting
open problem of combinatorics due to its vast
applications. In, [6], they studied the existence of
cyclic triple system over when .
While Colbourn and Rosa have given the spectrum
of , [7]. Recently, in, [8], they introduced
a new type of triple system called compatible
factorization. They employed the near-one-factor to
arrange
distinct triple into rows
according to certain conditions for
. In, [9] they developed the compatible
factorization to display
triples with
minimum repetition for .
The primary aim of this paper is to devise a
novel decomposition for the complete multigraph
utilizing wheel graphs of distinct orders.
Then we will employ this decomposition to define a
new cyclic triple system to arrange
triples satisfying certain constraints.
2 Preliminaries and Definitions
Here, we introduce some key ideas in
BIBD and graph decomposition that are
relevant to our conclusions. The primary goals of
this research will be achieved by applying the partial
difference approach, which is described in this
section and has been successful in creating cyclic
-designs in many cases,[9].
Definition 1 A wheel graph of order, written
as, is a graph that
contains a cycle of order , and each vertex in
the cycle is joined to a new vertex, , which is
known as center, [10].
Definition 2 A starter of cyclic -design is
the collection of subgraphs of that generates all
the subgraphs in , [11].
Definition 3 Let be a subgraph of . The list of
differences from is the multiset, [12],
In general, given a multiset of
subgraphs of , the list of differences of the
multiset is defined by:
.
Definition 4 Let be a subgraph of , the
stabilizer of under is
and is called trivial if
,[12].
As a particular result of, [13], we have the
following lemma.
Theorem 5 Let be even and be a multiset of
subgraphs of and every subgraph of has
trivial stabilizer. Then is a starter of
cyclic-design if and only if covers each
nonzero integer of
exactly and
occurs
times, [14].
Definition 6 Let be a -subset of . The list of
difference of is the multiset,[6],
.
Generally, if is a multiset of
-subsets of , then the list of differences of
multiset is defined as
.
Theorem 7 Let be even and be a multiset of -
subsets of . An is a starter of cyclic -fold
triple system if and only if covers each
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2023.22.104
Khaled Ahmad Matarneh, Mowafaq Omar Al-Qadri,
Abdallah Al-Husban, Raja'i Aldiabat,
Shameseddin Alshorm
E-ISSN: 2224-2880
951
Volume 22, 2023
nonzero integer,[6], of
exactly times and the
middle difference
precisely
times.
Definition 8 Let and be two -cycles of a
graph of order . Then and are called parallel
cycles if they have the same difference set, [15].
Definition 9 Let and be two -cycles of a
graph of order . If the sum of each two
corresponding vertices of them is , then it is called
adjoined -cycles,[15].
Lemma 10 Any two adjoined -cycles of a graph
are parallel -cycles, [15].
3 Cyclic -wheel
System of
In this section, we consider how to decompose the
complete multigraph into wheel graphs for
. According to the Definition 1, the edges
set of wheel graph will be
expressed below:
such that:
,
where
.
So, the list of difference from is
. We will call and
the cycle differences and
internal differences, respectively, of .
As usual, any is written as a permutation:
.
To simplify determining a vertex set and computing
the list of differences of -cycle, we will write
of high order, when, as linking paths as
follows:
, where are
positive integers and in which and
are paths and is a point such that:
, .
We represent a path of even order as follows:
,
Therefore, the list of difference and vertex set of
determined as:
,
Moreover, the difference between and that
located in the same cycle, denoted by , is
defined as the difference between the last vertex in
the path and the first vertex in the path . As a
result, the vertex set and list of difference for an -
cycle , , will be written as:
,
Definition 11 A
-wheel system of
is -design where is a collection of
wheels in which the order of each wheel graph
belong to .
We will denote of a cyclic
-wheel
system of by where is its a
starter set. Following Tian and Wei,[13], we will
use the notation
to
describe a set of subgraphs meaning that there
are subgraph of order , subgraph of order
, etc. For more see, [16].
The following results will be used to prove the
existence
-wheel system of ,
[17].
Lemma 12 Let be graph of order . Let be a
positive even and be a set of cycles of . Then
is near--factor if and only if the vertex set of
covers every element of exactly
times except
one vertex.
Proof. We will prove the first part of this lemma.
The second part can be shown similarly. Let
be a set of cycles that forms a near-
-factor, then each vertex of has a degree
except the isolated vertex. Let and is
not isolated vertex in . Then, the degree of in
is
.
Where and denote the degree of
in and respectively. Since a cycle graph is a
-regular graph, then according
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2023.22.104
Khaled Ahmad Matarneh, Mowafaq Omar Al-Qadri,
Abdallah Al-Husban, Raja'i Aldiabat,
Shameseddin Alshorm
E-ISSN: 2224-2880
952
Volume 22, 2023
to whether is a vertex of . Suppose the number
of cycles in that contains is . Then, we have:
.
Since, then
.
Lemma 13 Let and be even integers and
be a set of
wheels of . If the cycles
satisfy a near--factor, then the internal
differences,, of covers each element of
exactly times except the middle difference
, which occurs
times.
Proof. Let
be a set of wheels of such that the set of cycles
satisfies near--factor with
isolated. The internal differences of , , is
determined as follows:
,
Since the cycles form a near--
factor, then the vertex set of set of cycles
covers each element of exactly
times
except based on Lemma 12, [18].
Now if we label by, then every vertex of
will appear as exactly
times. Therefore,
can be written as:
Thus, every element in the multiset of
will be shown
times. Then
covers all the nonzero elements of
precisely times except the middle difference
occur
times, [19].
Lemma 14 Let be a wheel graph of . If
the is formed as , then
has a trivial stabilizer.
Proof. Let be -
wheel of , the stabilizer of is represented
as follows:
suppose , then.
This implies that . Hence, .
Now, we will present the existence cyclic
-wheel system of for
.
Theorem 15 For , there exists a cyclic
-wheel system of .
Proof. We construct the starter of cyclic
-wheel system of as
follows:
Case 1. .
Consider that is a wheel set
of such that:
,
,
,
,
,,
,
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2023.22.104
Khaled Ahmad Matarneh, Mowafaq Omar Al-Qadri,
Abdallah Al-Husban, Raja'i Aldiabat,
Shameseddin Alshorm
E-ISSN: 2224-2880
953
Volume 22, 2023
,
,
.
It is straightforward to check that
is the starter of cyclic
-wheel system of .
Case 2. is odd.
Consider that
is a set of
wheel of , where the list of wheels of order
is:
.
When
, let
.
Whereas,
and
are wheels of order in which the
paths
are represented below:
,
,
.
Meanwhile,
and
are considered
the wheel graph such that the paths
are written as:
,
,
,
,
.
In order to prove that
is a starter set of cyclic -
wheel system of , the differences list of
will be determined as follows:
we begin with the cycle differences as
follows:
,
Such that
, where
,
,
.
,
,
,
,
,
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2023.22.104
Khaled Ahmad Matarneh, Mowafaq Omar Al-Qadri,
Abdallah Al-Husban, Raja'i Aldiabat,
Shameseddin Alshorm
E-ISSN: 2224-2880
954
Volume 22, 2023
,
,
,
.
when
,
.
Since
and
are
adjoined -cycles and -cycles
respectively, then
and
based on Lemma 10. Hence,
it is sufficient to determine the lists of
and
as follows:
.
.
For simplicity,
can be written as:
Equally,
is computed as:
.
Such that
,
,
.
.
Furthermore, the differences list of
can be
expressed as:
.
In view of the former investigations, it can be
noticed that the cycle differences of ,
, covers each nonzero integer of
four times and the middle difference
occurs twice.
On the other hand, it is easy to prove that the
vertex set of cycles associated with the set of wheel
graphs contains each element in
precisely
twice, then it satisfy a near-four-factor by Lemma
12. Based on Lemma 13, the internal differences of
covers each element of
four times and the
middle difference occurs twice, [20]
Since wheel graph in has a trivial stabilizer by
Lemma 14, then the set of wheel graphs is the
starter set of -wheel system of
based on Theorem 5.
Case 3. is even.
Consider that
is a set of
wheels of . Where the wheels of order
and ,
, are the same wheels that
mentioned in Case 2 with slightly different in the
list of wheels of order as follows:
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2023.22.104
Khaled Ahmad Matarneh, Mowafaq Omar Al-Qadri,
Abdallah Al-Husban, Raja'i Aldiabat,
Shameseddin Alshorm
E-ISSN: 2224-2880
955
Volume 22, 2023
.
When
, let
.
Meanwhile, the wheels of order are
and
in which the paths
are represented below:
,
,
,
,
.
Similarly, by following the same strategy used Case
2, it is easy to check that the set of wheel graph
is a starter of cyclic
-wheel system of
when is an even.
4 Cyclic Triple Factorization
We provide a new idea in this section called cyclic
triple factorization, which is a kind of cyclic triple
system. The decomposition of all triples into
cyclic triple systems will be based on this novel
method, [21].
Definition 16 A cyclic triple factorization with
order v, labelled as involves the
arrangement of triples into rows
while meeting the specified conditions:
(i) Object appears precisely times
in each row .
(ii) Each object except appears four times in
each row .
(iii) The triples associated with row contains
no repetitions.
Note that condition in Definition 16 means
that the triples in row , for are distinct
but not in whole array. The
construction of cyclic wheel system of will be
employed to prove the existence of a cyclic triple
factorization of order in the following
theorem.
Theorem 17 For , there exists a near triple
factorization of order .
Proof. To construct, we need to have
rows and columns based on
Definition 16. Consider the starter set
of -wheel
system of that constructed in Theorem 15.
To construct , we partition the wheel
graphs of into separated triangles (triples) by
combining the centre of each wheel with every edge
of its cycle. Hence, the number of triples of each
row is equal to the number of edges of the cycles
associated with the wheels in . Since the cycles
set associated with the wheel graphs of is
, then the number of the
columns is computed as the following formula:
.
Therefore, the center vertex in each row
, will appears times in the
generated triples while other vertices will appear
four times since the cycles set satisfies a near-four-
factor. On the other hand, all the triples in each row
are distinct since there is no edge in
that it has the same endpoints.
Then all conditions of are satisfied for
.
Example 18 Let and
be a set of wheel graph of such
that:
,
,
,
,
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2023.22.104
Khaled Ahmad Matarneh, Mowafaq Omar Al-Qadri,
Abdallah Al-Husban, Raja'i Aldiabat,
Shameseddin Alshorm
E-ISSN: 2224-2880
956
Volume 22, 2023
, ,
,
,
,
.
From Lemma 12, is a
starter set of cyclic -wheel system
of, that generates its wheels
by adding one modular. To construct,
we partition all wheel graphs of
into separate triangles (triples). Figure 1 shows that
how the wheel graph can be partitioned into
separate triples.
Fig. 1: Partition wheel graph into triples
Similarly, we can partition the remaining wheels
of into triples in the same way.
Clearly, it can be noticed that the center of the
wheels in each row , , of
will appear in triples, the
number of edges of cycles that
associated with , and other vertices appear four
times since the cycles set satisfies near-four-factor.
Table 1 (Appendix) shows the construction of
.
In a -fold triple system, denoted as ,
it is important to revisit the definition, wherein it is
characterized as a pair . Here, represents a
set of elements, and constitutes a collection of
-subsets of , referred to as triples. Notably, each
pair of distinct elements from is precisely found
together in triples within . Therefore, no
collection of triples may be regarded as a
Consequently, it is reasonable to inquire if the -
fold triple system, is formed via the
creation of cyclic triple factorization. We must
demonstrate that has a balanced quality,
namely that each pair of unique elements of v
belongs to exactly triples, in order to demonstrate
that is The difference set
approach will be used in this manner.
Definition 6 and Theorem 7 state that building an
appropriate triples set is equivalent to the
presence of a -fold cyclic triple system, .
such that the list of differences covers every
nonzero element of
exactly times except the
middle difference
, which occurs
times.
Theorem 19 For , there exists a -fold
cyclic triple factorization of order .
Proof. Let
be the starter
of -wheel system of
mentioned in Theorem 15. Then, the list of
differences:
covers each nonzero integer of eight times
and the middle difference four times in which the
cycle differences and the internal
differences have the same list of
differences. Let be the set of the generated triples
from partition of the wheels in , then the triples of
will be formed by linking every two internal
edges with an edge that connected them. As shown
in Figure 1, each internal edge of will appear
twice in while the edge set of cycles associated
with will occur once. Hence, the list of
differences of , , contains twice and
once. Therefore, covers each
nonzero integer of twelve times and the
middle difference six times. Based on
Theorem 2.8, the set of triples is the starter of
cyclic -fold triple system of order such that
satisfies near triple factorization conditions.
5 Algorithm of Starter Triples of
In this section, we use the starter cycles of
to develop and formulate the
algorithm of starter triples of .
The process of formulating an algorithm for the
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2023.22.104
Khaled Ahmad Matarneh, Mowafaq Omar Al-Qadri,
Abdallah Al-Husban, Raja'i Aldiabat,
Shameseddin Alshorm
E-ISSN: 2224-2880
957
Volume 22, 2023
starter triples will be split into three cases
depending on .
Case 1. .
See Example 4.3, and Table 1 (Appendix).
Case 2. is odd.
The starter of is formed by
partition the starter set
of
-wheel system of .
Thus, we start with the generated triple from
partition of wheels of order , , as follows:
,
,
,
,
.
Furthermore, the list of generated triples from
wheels of order ,
could be expressed as
follows:
,
,
,
,
.
Similarly, the produced triples from the wheels
of order ,
that could be
represented in the following subsets:
,
,
,
,
,
.
For simplicity, we will link the subsets together
which have a relationship between their triples. As a
result, the algorithm of the starter triples of
, can be formulated as:
Such that:
,
.
Case 3. is even.
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2023.22.104
Khaled Ahmad Matarneh, Mowafaq Omar Al-Qadri,
Abdallah Al-Husban, Raja'i Aldiabat,
Shameseddin Alshorm
E-ISSN: 2224-2880
958
Volume 22, 2023
By following the same strategy of Case, the
algorithm of starter triples of a,
will be formulated as such that
,
,
.
6 Conclusion
In this paper, we have investigated new
decomposition of complete multigraph. Especially,
we have decomposed of into wheel graphs for
. We have also defined and proven
the existence of cyclic triple factorization, ,
for along with the construction of
has been demonstrated that is a
cyclic -fold triple system. Then, the algorithms of
the starter triples of have been
formulated. We expect the construction of
will be simple and can be extended
it for all even cases,.
References:
[1] R. M. Wilson, “Decompositions of complete
graphs into subgraphs isomorphic to a given
graph,” in Proc. 5th British Combinatorial
Conf., 1975.
[2] Z. Liang and J. Guo, “Decomposition of
complete multigraphs into crown
graphs,” Journal of Applied Mathematics and
Computing, vol. 32, pp. 507-517, 2010.
[3] M. Tarsi,” Decomposition of a complete
multigraph into simple paths: non balanced
handcuffed designs,” Journal of
Combinatorial Theory, Series A, vol. 34, pp.
60-70, 1983.
[4] V. Chitra and A. Muthusamy, “Symmetric
Hamilton cycle decompositions of complete
multigraphs,” Discussiones Mathematicae
Graph Theory, vol. 33, pp. 695-707, 2013.
[5] Z. Tian and R. Wei, “Decomposing triples
into cyclic designs,” Discrete Mathematics,
vol. 310, pp. 700-713, 2010.
[6] M. J. Colbourn and C. J. Colbourn, “Cyclic
block designs with block size 3,” European
Journal of Combinatorics, vol. 2, pp. 21-26,
1981
[7] C. J. Colbourn and A. Rosa, Triple systems.
USA: Oxford University Press, 1999
[8] H. Ibrahim and W. D. Wallis, “An
enumeration of triad designs,” J.
Combinatorics Information and System
Sciences, pp. 5-17, 2005.
[9] R. Aldiabat and H. Ibrahim, “Near-compatible
factorization,” International Journal of Pure
and Applied Mathematics, vol. 120, pp. 259-
272, 2018.
[10] S. Pemmaraju and S. Skiena, “Cycles, stars,
and wheels,” Computational Discrete
Mathematics Combinatorics and Graph
Theory in Mathematica, pp. 284-249, 2003
[11] S. L. Wu and D. M. Lee, “K-cyclic even cycle
systems of the complete graph,” Taiwanese
Journal of Mathematics, vol. 12, pp-137,
2008.
[12] Z. Liang, “On cyclic decompositions of the
complete graph into the 2-regular graphs,”
Journal of Applied Mathematics and
Computing, vol. 24, pp. 261-271, 2007.
[13] M. Buratti, S. Capparelli and A. Del Fra,
“Cyclic Hamiltonian cycle systems of the λ-
fold complete and cocktail party
graphs,” European Journal of
Combinatorics, vol. 31, pp. 1484-1496, 2010.
[14] M. Buratti, “A description of any regular or 1-
rotational design by difference
methods,” Booklet of the abstracts of
Combinatorics, pp. 35-52, 2000.
[15] M. Alqadri and H. Ibrahim, “A near cyclic
-cycle system of complete
multigraph,” Far East Journal of
Mathematical Sciences (FJMS). Vol. 101, pp.
1671-1390, 2017.
[16] Alshorm, S.M. (2023). Groups in Which the
Commutator Subgroup is Cyclic. In: Zeidan,
[17] D., Cortés, J.C., Burqan, A., Qazza, A.,
Merker, J., Gharib, G. (eds) Mathematics and
Computation. IACMC 2022. Springer
Proceedings in Mathematics & Statistics, vol
418. Springer, Singapore.
https://doi.org/10.1007/978-981-99-0447-
1_33
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2023.22.104
Khaled Ahmad Matarneh, Mowafaq Omar Al-Qadri,
Abdallah Al-Husban, Raja'i Aldiabat,
Shameseddin Alshorm
E-ISSN: 2224-2880
959
Volume 22, 2023
[18] Alsarahead, Mikhled Okleh, and Abdallah Al-
Husban. "Complex multi–fuzzy
subgroups." Journal of Discrete Mathematical
Sciences and Cryptography 25, no. 8 (2022):
2707-2716.
[19] Al-Ηusban, A. (2022). Fuzzy Soft Groups
Based on Fuzzy Space. WSEAS Transactions
on Mathematics, 21, 53-57.
[20] Alqadri, M., Ibrahim, H., & Karim, S. (2020).
Cyclic Triple Factorization. IAENG
International Journal of Applied
Mathematics, 50(4), 1-12.
[21] Alqadri, M., & Ibrahim, H. (2017,
November). On the cyclic decomposition of
complete multigraph into near Hamiltonian
cycles. In AIP Conference Proceedings (Vol.
1905, No. 1). AIP Publishing.
APPENDIX
Table 1. Case 1. .
Contribution of Individual Authors to the
Creation of a Scientific Article (Ghostwriting
Policy)
Khaled Matarneh did Formal analysis and funding
acquisition, Mowafaq Al-Qadri did Investigation
and Methodology, Abdallah Al-Husban did project
administration and resources, Shameseddin Alshorm
do software, supervision and validation.
Sources of Funding for Research Presented in a
Scientific Article or Scientific Article Itself
The authors would like to thank the Arab Open
University in Saudi Arabia for supporting this
research paper
Conflict of Interest
The authors have no conflicts of interest to declare.
Creative Commons Attribution License 4.0
(Attribution 4.0 International, CC BY 4.0)
This article is published under the terms of the
Creative Commons Attribution License 4.0
https://creativecommons.org/licenses/by/4.0/deed.en
_US
WSEAS TRANSACTIONS on MATHEMATICS
DOI: 10.37394/23206.2023.22.104
Khaled Ahmad Matarneh, Mowafaq Omar Al-Qadri,
Abdallah Al-Husban, Raja'i Aldiabat,
Shameseddin Alshorm
E-ISSN: 2224-2880
960
Volume 22, 2023
