## Akcije

kako citirati ovaj članak
prikaži na oba jezika
podeli ovaj članak

## Metrika

• citati u SCIndeksu: 0
• citati u CrossRef-u:0
• posete u poslednjih 30 dana:5
• preuzimanja u poslednjih 30 dana:3   članak: 1 od 1 povratak na rezultate
2022, vol. 70, br. 3, str. 583-597
Dominacija na petougaonim kaktus-lancima
Visoka škola za poslovnu ekonomiju i preduzetništvo, Beograd

Ključne reči: graf; petougaoni kaktus-lanac; dominantni skup; dominacijski broj
Sažetak
Graf kao matematički objekat zauzima posebno mesto u nauci. Teorija grafova nalazi sve veću primenu u mnogobrojnim sferama poslovanja, kao i naučnim oblastima. U ovom radu analizirani su petougaoni kaktus-lanci koji predstavljaju posebnu vrstu grafa sastavljenog od petougaonih ciklusa u kojima dva susedna ciklusa imaju zajednički samo jedan čvor. Cilj istraživanja jeste određivanje dominantnog skupa i dominacijskog broja na orto i meta petougaonim kaktus-lancima. Metode: Kada se odgovarajuća odredišta tretiraju kao čvorovi grafa, a veze među njima kao grane u grafu, dobija se potpuna struktura grafa na koju se primenjuju zakonitosti teorije grafova. Temena petougla su tretirana kao čvorovi grafa, a stranice kao grane u grafu. Primenom matematičkih metoda određena je dominacija na jednom petouglu, zatim na dva petougla sa zajedničkim čvorom, a nakon toga na orto i meta petougaonim kaktus-lancima. Rezultati: Istraživanja su pokazala da je dominacijski broj na orto lancu Oℎ dužine h ≥2 jednak vrednosti izraza ⌈ 3ℎ 2 ⌉, dok je na meta lancu Mℎ jednak vrednosti izraza h + 1, što je dokazano u radu. Zaključak: Rezultati pokazuju da su dominantni skupovi i dominacijski brojevi na orto i meta petougaonim kaktus-lancima određeni i eksplicitno iskazani matematičkim izrazima. Takođe, upućuju na mogućnost njihove primene u oblastima nauke, kao i u sferama poslovanja u kojima se pojavljuju ove strukture.

# Introduction

Mathematical apparatus and mathematical methods are used in almost all fields of science, both natural (Ghergu & Radulescu, 2011; Veličković et al, 2020) and social (Vladimirovich & Vasilyevich-Chernyaev, 2021). A graph as a mathematical object occupies a special place in science (Bakhshesh, 2022; Hajian & Rad, 2021; Hernández Mira et al, 2021). It is used in medicine, genetics, chemistry, etc. All structural formulas of covalently bound compounds are graphs. Chemical elements are represented by graphs where atoms are vertices and chemical bonds are lines in the graph (Balaban, 1985). A graphical representation of chemical structures provides a visual insight into molecular bonds and chemical properties of molecules. The QSPR study has shown that many of chemical properties of molecules are closely related to theoretical graphical invariants called molecular descriptors (Mihalić & Trinajstić, 1992). The theoretical graphical invariant is also the dominance number, which is the simplest variant of the k-dominance number that is used many times in mathematics (Zmazek & Žerovnik, 2003).

A graph is usually denoted by G, a set of its vertices (nodes) by V(G) and a set of its branches (lines) by E(G).

A set D that is a subset of the set V(G) is called a k-dominant set in the graph G if for each vertex outside the set D there is at least one vertex in the set D such that the distance between them is less than or equal to k. The number of elements of the smallest k-dominant set is called the kdominance number and is denoted by yk. If k = 1, the 1-dominance number is called the dominance number and is denoted by γ and the 1-dominant set is called the dominant set.

A cactus graph is a connected graph in which no line (branch) is in more than one cycle. The study of cactus graphs began in the middle of the 20th century. In his work (Husimi, 1950) Husimi uses these graphs in studies of cluster integrals. Riddell (Riddell, 1951) uses them in the theory of condensation. They were later used in the theory of electrical and communication networks (Zmazek & Zerovnik, 2005) as well as in chemistry (Sharma et al, 1997; Gupta et al, 2001; Gupta et al, 2002).

It is known that many chemical compounds have a pentagonal shape in their configuration. Among them are cycloalkanes, which are very common compounds in the nature. The five-membered and six-membered cycloalkanes, cyclopentane (Figure 1) and cyclohexane, which contain 5 and 6 ring carbon atoms, respectively, are very stable and their structures appear in many biological molecules.  Figure 1 Cyclopentane
Рис. 1 – Циклопентан
Слика 1 – Циклопентан

Their ring structures are also included in the composition of steroids. A large number of steroids are synthesized in laboratories and used in the treatment of cancer, arthritis, various allergies and other diseases (Balaban & Zeljković, 2021). Pentagonal forms in combination with hexagonal forms are present in many compounds, among which are heterocyclic compounds: morphine, benzofuran, dibenzothiophene and others.

In this paper, we analyze the k-dominance of pentagonal cactus chains. Hexagonal cactus chains were investigated in papers (Farrell, 1987; Vukičević & Klobučar, 2007). Afterwards, the papers (Majstorovic et al, 2012; Klobučar & Klobučar, 2019) determined the dominance number on a uniform hexagonal cactus chain, the dominance number on an arbitrary hexagonal network, and the total and double total dominance number on a hexagonal network. The K-dominance on rhomboidal cactus chains (Carević et al, 2020) as well as on the icosahedral-hexagonal network (Carević, 2021) was also investigated.

# Pentagonal cactus-chains

The pentagonal cactus-chain G is a graph consisting of a cycle with 5 vertices. A vertex that is common to two or three pentagons is called a cutvertex. If each pentagon in the graph G has at most 2 cut-vertices and each cut-vertex is divided between exactly 2 pentagons, the graph G is called a pentagonal cactus-chain.

With G we will denote a pentagonal cactus-chain of the length h and G= 𝑃1𝑃2 ... 𝑃 where 𝑃i are successive pentagons in the chain (Figure 2).  Figure 2 Pentagonal cactus-chain of the length 7
Рис. 2 – Пятиугольная кактус-цепочка длиной 7
Слика 2 – Петоугаони кактус-ланац дужине 7

Denote by x and y the vertices in the graph G and by d(x, y) the distance between them, where the distance between two vertices is equal to the number of branches located from one vertex to another. Denote by 𝑃i the minimum distance between the pentagons pi and pi+2:

$$p_i = min \{d(x,y): x \in P^{i} \wedge y \in P^{i+2},i = 1, 2, ... , h - 2\}$$

Then 𝑃i is the distance between the pentagons 𝑃i and 𝑃i+2.

With the exception of the first and last pentagons in the cactus chain, which have one cut-vertex, all other pentagons have two cut-vertices, and they are called inner pentagons.

In the pentagonal cactus chain G, we distinguish between ortho and meta inner pentagons. An inner pentagon is called an ortho pentagon if its cut-vertices are adjacent, and a meta pentagon if the distance between its cut-vertices is d = 2.

A pentagonal cactus chain is uniform if all its inner pentagons are of the same type. A chain G is called an ortho-chain, and is denoted by O if all its inner pentagons are ortho-pentagons (Figure 3).  Figure 3 Ortho cactus-chain 𝑂5
Рис. 3 – Орто-кактус-цепочка 𝑂5
Слика 3 – Орто кактус-ланац О5

Analogously, a chain G is called a meta-chain, and is denoted by M if all its inner pentagons are meta-pentagons (Figure 4).  Figure 4 Meta cactus-chain 𝑀5
Рис. 4 – Мета кактус-цепочка М5
Слика 4 – Мета кактус-ланац М5

To determine the dominant set on the uniform pentagonal cactus chains O and M, it will be necessary to point out certain vertices in the cactus chain. That is why it is necessary to mark them. In the ortho pentagon pi the cut-vertices are adjacent and we will denote them by Vi and Vi+1. The other vertices in 𝑃i it will be denoted by $$x_{1}^{i}, x_{2}^{i}$$ and $$x_{3}^{i}$$ (Figure 5):  Figure 5 Marking vertices in the ortho pentagon
Рис. 5 – Обозначение вершин в ортогональном пятиугольнике
Слика 5 – Означавање чворова у орто петоуглу

In the meta pentagon 𝑃i the cut-vertices are at a distance d = 2 and we will denote them by V2i −1 and V2i +1. With V2i we will denote the vertex to which it applies d(𝑉2𝑖−1, 𝑉2𝑖) = d(𝑉2𝑖, 𝑉2𝑖+1) = 1.  Figure 6 Marking vertices in the meta pentagon
Рис. 6 – Обозначение вершин в мета-пятиугольнике
Слика 6 – Означавање чворова у мета петоуглу

The other two nodes in the pentagon 𝑃i will be denoted $$x_{1}^{i}$$ and $$x_{2}^{i},$$ (Figure 6):

# Research results

In this section, we consider 1-dominance on ortho and meta pentagonal cactus chains. We will first consider the dominance of one pentagon and two adjacent pentagons in the ortho and meta chain of cacti.

Lemma 3.1. The dominance number for the pentagon is γ = 2.

Proof: Let us denote the vertices of the pentagon by 𝑥1, 𝑥2, 𝑥3, 𝑥4, 𝑥5 (Figure 7):  Figure 7 Dominant set on a pentagon
Рис. 7 – Доминирующее множество на пятиугольнике
Слика 7 – Доминантни скуп на петоуглу

One pentagon vertex dominates two adjacent vertices. Let us take the vertex 𝑥1. It dominates the vertices 𝑥2 and 𝑥5. As the pentagon has 5 vertices, domination over the other two vertices 𝑥3 and 𝑥4 is necessary. We conclude that one of the remaining two vertices must belong to the dominant set on the pentagon. Let it be the vertex 𝑥3. Thus, the set D = {𝑥1, 𝑥3} is the dominant set for a given pentagon but it is not the only dominant set whose cardinality is equal to 2. They are also sets that contain any two non-adjacent pentagon vertices. Let us prove that any of the mentioned two-membered sets is the minimum dominant set on the pentagon. Assuming that there is a dominant set of less cardinality D', it would have to contain only one vertex and one vertex cannot dominate the remaining 4 vertices of the pentagon. Thus, the minimum dominant set on a pentagon is a two-membered set, so the dominance number for the pentagon is 𝛾 = 2.

Lemma 3.2. The dominance number for two pentagons with one cut-vertex is 𝛾 = 3.

Proof: Let us denote the vertices of two pentagons by one common vertex with 𝑥1, 𝑥2, . . . , 𝑥9 (Figure 8):  Figure 8 Dominant set for two pentagons with a cut-vertex
Рис. 8 – Доминирующее множество для двух пятиугольников с пересекающейся вершиной
Слика 8 – Доминантни скуп за два петоугла са пресеченим чвором

Let 𝑥1 be the cut-vertex of the given pentagons 𝑃1 and 𝑃2. Based on Lemma 3.1. the pentagon 𝑃1 excluding the vertex 𝑥1 must have another dominant vertex that is not adjacent to the vertex 𝑥1. Let it be the vertex 𝑥3. Also by applying Lemma 3.1. the pentagon 𝑃2 excluding the vertex 𝑥1 must have another dominant vertex that is not adjacent to the vertex 𝑥1. Let it be the vertex 𝑥7. Thus the nodes 𝑥1, 𝑥3 and 𝑥7 dominate over the nodes 𝑥2, 𝑥4, 𝑥5, 𝑥6, 𝑥8 and 𝑥9 so the dominant set for the pentagons 𝑃1𝑃2 is the set D = {𝑥1,𝑥3, 𝑥7}. Analogous to the consideration in Lemma 3.1. the set D is not the only three-membered set that is dominant on 𝑃1𝑃2but there is no dominant set of less cardinality. Suppose that there is a dominant set D' whose cardinality is equal to 2. Let D' contain one vertex from each pentagon, for example 𝐷′ = {𝑥1,𝑥3}.The vertices 𝑥1 and 𝑥3 would then dominate over the remaining 7 vertices in 𝑃1𝑃2 and this is impossible. The vertex 𝑥1 as a common vertex for both pentagons dominates over two neighboring vertices in both pentagons, so it dominates over 4 vertices in 𝑃1𝑃2.The vertex 𝑥3, or any other vertex not adjacent to the vertex 𝑥1 dominates two adjacent vertices. So, the total sum of vertices covered by dominance is 4 + 2 = 6 and that is less than 7. Thus, 2 vertices cannot dominate the remaining 7 vertices in 𝑃1𝑃2. We conclude that the minimum dominant set for 𝑃1𝑃2 is a three-membered set and 𝛾 = 3.

Let us consider the dominance on pentagonal ortho and meta cactus chains of arbitrary length.

Theorem 3.1. $$y(O_h) = ⌈\frac{3h}{2}⌉$$ for each $$h≥ 2 ˄ h \in N$$.

Proof: We observe a pentagonal ortho cactus-chain 𝑂 = 𝑃1𝑃2 ... 𝑃 (Figure 9) and a set:  Figure 9 Minimum dominant set for 𝑂
Рис. 9 – Минимально доминирующее множество для 𝑂
Слика 9 – Минимални доминантни скуп за О

$$D_{O_{h}} = \left \{ x_{2}^{i}, i= 1,h \right \}\cup \left \{ V_{2i}, i= 1, \left \lceil \frac{h}{2} \right \rceil \right \}$$

Let us prove that $$D_{O_{h}}$$ is the dominant set of minimum cardinality for a pentagonal ortho cactus-chain 𝑂= 𝑃1𝑃2… 𝑃.

Let us divide the ortho-chain 𝑂 into subchains 𝑃2𝑖−1𝑃2𝑖, i = 1, 2, ... , ⌊$$\frac{h}{2}$$⌋ (Figure 10) and the last pentagon 𝑃 if h is an odd number.  Figure 10 Subchain of the ortho-chain 𝑂
Рис. 10 – Подцепочка орто-цепочки 𝑂
Слика 10 – Подланац орто ланца 𝑂

Based on Lemma 3.2. the set 𝐴𝑖 = {$$x_{2}^{2i-1}, x_{2}^{2i}, V_{2i}$$} for i = 1, 2, ... , ⌊$$\frac{h}{2}$$⌋ is the dominant set of minimum cardinality for the subchain 𝑃2𝑖−1𝑃2𝑖. An ortho-chain of the length h for h = 2k, k ϵ N is composed of $$\frac{h}{2}$$ subchains 𝑃2𝑖−1𝑃2𝑖, i = 1, 2, ... , $$\frac{h}{2}$$ (Figure 9A), so the set

$$D_1 = \bigcup_{i= 1}^{k}A_i, \ for \ k= \frac{h}{2}$$

is a dominant set for the ortho-chain O. Therefore, it is

$$y(O_h)\leq card(D_1)= \frac{h}{2}\cdot 3= \frac{3h}{2}$$

where we have marked the cardinality of the set 𝐷1 with card(𝐷1).

If h is an odd number (Figure 9B), then the set

$$D_2= \bigcup_{i= 1}^{k}A_i\cup \left \{ x_{2}^{h}, V_{h+1} \right \}, \ for \ k= \left \lfloor \frac{h}{2} \right \rfloor$$

is a dominant set for the ortho-chain 𝑂 and then is

$$y(O_h)\leq card(D_2)= \left \lfloor \frac{h}{2} \right \rfloor\cdot 3+2 = \left \lceil \frac{3h}{2} \right \rceil .$$

Note that the set 𝐷1 for k = $$\frac{h}{2}$$ if h an even number is equal to the following expression:

$$D_1\bigcup_{i= 1}^{k}A_i= \bigcup_{i= 1}^{k}\left \{ x_{2}^{2i-1}, x_{2}^{2i}, V_{2i} \right \} =$$
$$= \left \{ x_{2}^{1}, x_{2}^{2}, V_{2} \right \}\cup \left \{ x_{2}^{3}, x_{2}^{4}, V_{4} \right \}\cup ...\cup \left \{ x_{2}^{h-1}, x_{2}^{h}, V_{h} \right \} =$$
$$= \left \{ x_{2}^{i}, i= 1,2,...,\frac{h}{2} \right \}$$

Also for k = ⌊$$\frac{h}{2}$$⌋ and h is an odd number, the set 𝐷2 is equal to the following expression:

$$D_2\bigcup_{i= 1}^{k}A_i\cup \left \{ x_{2}^{h}, V_{h+1} \right \} =D_2\bigcup_{i= 1}^{k}A_i\cup \left \{ x_{2}^{h}, V_{h+1} \right \} =$$
$$= \bigcup_{i= 1}^{k}\left \{ x_{2}^{2i-1}, x_{2}^{2i}, V_{2i} \right \}\cup \left \{ x_{2}^{h}, V_{h+1} \right \}=$$
$$= \left \{ x_{2}^{1}, x_{2}^{2}, V_{2} \right \}\cup \left \{ x_{2}^{3}, x_{2}^{4}, V_{4} \right \}\cup ...\cup \left \{ x_{2}^{h-1}, x_{2}^{h}, V_{h} \right \} \cup \left \{ x_{2}^{h}, V_{h+1} \right \}=$$
$$= \left \{ x_{2}^{i}, i= 1,2,...,h \right \}\cup \left \{ V_{2i}, i= 1,2,...,\left \lceil \frac{h}{2} \right \rceil \right \}$$

In case h is an even number, $$\frac{h}{2}= ⌈\frac{h}{2}⌉$$ then we conclude that it is 𝐷1= 𝐷2.

So, the set $$D_{O_{h}}$$= { $$𝑥_2^𝑖$$, i = 1, h} ∪ { 𝑉2𝑖, i = 1, $$⌈\frac{h}{2}⌉$$} is the dominant set for the ortho-chain 𝑂 when h is even or odd number.

Also, in the case where h is an even number, $$\frac{3h}{2}= ⌈\frac{3h}{2}⌉$$. So, 𝛾(Oh) ≤$$⌈\frac{3h}{2}⌉$$ when h is even or odd number. Prove that the set $$D_{O_{h}}$$ is the dominant set of minimal cardinality. Each subchain 𝑃2𝑖−1𝑃2𝑖 contains 3 dominant nodes based on Lemma 3.2. Based on this, we conclude that each dominant set on the chain 𝑂 contains more than 3 or exactly 3 dominant nodes in each subchain 𝑃2𝑖−1𝑃2𝑖 and more than 2 or exactly 2 dominant nodes in the last pentagon if h is an odd number, based on Lemma 3.1. So, we conclude that it is 𝛾(Oh) ≥$$\frac{h}{2}$$∙ 3 in case h is an even number, and 𝛾(Oh) ≥$$\frac{h}{2}$$∙ 3 + 2 in case h is an odd number. When we combine both cases, we get that 𝛾(Oh) ≥ $$⌈\frac{3h}{2}⌉$$.

It follows from 𝛾(𝑂) ≤ $$⌈\frac{3h}{2}⌉$$ and 𝛾(𝑂) ≥ $$⌈\frac{3h}{2}⌉$$ that it is 𝛾(𝑂) = $$⌈\frac{3h}{2}⌉$$.

Corollary 3.1. $$D_{O_{h}}\subset D_{O_{h+1}}$$ for each $$h ≥ 2 ˄ h \in N$$.

Theorem 3.2. $$y(M_h) = h + 1$$ for each $$h ≥ 2 ˄ h \in N$$.

Proof: We observe a pentagonal meta cactus-chain 𝑀 = 𝑃1𝑃2... 𝑃(Figure 11) and set:  Figure 11 Minimum dominant set for 𝑀
Рис. 11 – Минимально доминирующее множество для 𝑀
Слика 11 – Минимални доминантни скуп за М

$$D_{M_h}= \left \{ V_{2i-1}, i= 1, h+1 \right \}$$

Let us prove that $$D_{M_h}$$ is the dominant set of minimum cardinality for a pentagonal meta cactus-chain 𝑀= 𝑃1𝑃2… 𝑃. Based on Lemma 3.1. each pentagon has a dominant set made up of two non-adjacent vertices. Thus, the set { 𝑉2𝑖−1, 𝑉2𝑖+1} is dominant for the pentagon 𝑃𝑖 for each i = 1, h. By merging the dominant sets of all pentagons in the chain, we get a set that is dominant for the whole chain. But, each pentagon 𝑃𝑖 has a common vertex with the pentagon 𝑃𝑖+1 for each i = 1, h ‒ 1. Common vertices should not be repeated in the dominant set. So, the set

$$D_{M_h}= \bigcup_{i= 1}^{h}\left \{ V_{2i-1}, V_{2i+1} \right \} \setminus \bigcup_{i= 1}^{h-1}\left \{ V_{2i+1} \right \}$$

is the dominant set for the meta-chain 𝑀.

Note that it is

$$D_{M_h}= \bigcup_{i= 1}^{h}\left \{ V_{2i-1}, V_{2i+1} \right \} \setminus \bigcup_{i= 1}^{h-1}\left \{ V_{2i+1} \right \} =$$
$$\left \{ \left \{ V_1,V_3 \right \}\cup \left \{ V_3,V_5 \right \}\cup \left \{ V_5,V_7 \right \}\cup ...\cup \left \{ V_{2h-1}, V_{2h+1} \right \} \right \}\setminus \left \{ V_3,V_5,V_7,...,V_{2h-1} \right \}=$$
$$\left \{ V_1,V_3,V_5,...,V_{2h-1},V_{2h+1} \right \}= \left \{ V_{2i-1}, i= 1, h+1 \right \}$$

Thus, the set $$D_{M_h}= \{ V_{2i-1}, i = 1, h + 1\}$$ is the dominant set for the meta-chain 𝑀 for each $$h \in N$$ and $$h ≥2$$. Let us prove that $$D_{M_h}$$ is the dominant set of minimal cardinality. Suppose that there is a set S of less cardinality that is dominant on the meta-chain 𝑀. The set S would then have one node less than the set $$D_{M_h}$$. Let it be a vertex 𝑉2𝑖+1 for any i = 1, h. Then the pentagon 𝑃𝑖 would have only one dominant node 𝑉2𝑖−1. Based on Lemma 3.1. that is not possible. We conclude that $$D_{M_h}$$ is the minimum dominant set for 𝑀 so it is 𝛾(𝑀) = h + 1.

Corollary 3.2. $$D_{M_h} ⊂ D_{M_h+1}$$ for each $$h ≥ 2 ˄ h \in N$$.

# Conclusion

In this paper, we have shown the arrangement of vertices in dominant sets on uniform ortho and meta pentagonal cactus chains that appear in molecule structures of numerous compounds. We also proved that the dominance number for a pentagonal ortho-chain of the length h is equal to the value of the expression $$⌈\frac{3h}{2}⌉$$ while for a pentagonal meta-chain it is equal to h + 1.