A secure set S⊆V of a graph G=(V,E) is a set whose every nonempty subset can be successfully defended from an attack, under appropriate definitions of ‘attack’ and ‘defense’. The set S is secure when ...|NX⋂S|≥|NX−S| for every X⊆S. A set S⊆V is secure dominating if it is both secure and dominating. The minimum cardinality of a secure set in G is the security number of G, s(G), and the minimum cardinality of a secure-dominating set in G is the secure domination number of G,γs(G). In this paper, we initiate a study of these parameters in the well-known Sierpiński graphs.
Let H be an arbitrary graph with vertex set V (H) = nH
= {1,..., nH
}. The generalized Sierpiński graph
S
H
n
, is defined on the vertex set nH
ⁿ, two different vertices u = un ... u₁ and υ = υn ... ...υ₁ being adjacent if there exists an h ∈ n such that (a) ut = υt
, for t > h, (b) uh
≠ υh
and uhvh
∈ E(H), and (c) ut = υh
and υt
= υh
for t < h. If H is the complete graph Kk
, then we speak of the Sierpiński graph
S
k
n
. We present an algorithm that recognizes Sierpiński graphs
S
n
n
in
O
(
|
V
(
S
k
n
)
|
1
+
1
/
n
)
=
O
(
|
E
(
S
k
n
)
|
)
time. For generalized Sierpiński graphs
S
H
n
we present a polynomial time algorithm for the case when H belong to a certain well defined class of graphs. We also describe how to derive the base graph H from an arbitrarily given
S
H
n
.
On the AVDTC of Sierpiński-type graphs Palma, Miguel A.D.R.; León, Adriana J.; Dantas, Simone
Discrete Applied Mathematics,
03/2024, Letnik:
346
Journal Article
Recenzirano
The Adjacent-Vertex-Distinguishing Total Coloring (AVDTC) conjecture asserts that every simple graph can be colored with an AVDTC using at most Δ+3 colors. We show that this conjecture is satisfied ...for all the Sierpiński graphs Spn, their regularizations +Spn and ++Spn and the fractals obtained as limit space of these graphs. Moreover, we construct explicit total colorings (with at most Δ+2 colors) for Sierpiński triangles graphs STpn and Sierpiński triangle fractal with the limit space STp∞, for p∈{3,4,5,6}, and prove that the AVDTC conjecture is also valid for these cases.
The purpose of this survey is to bring some order into the growing literature on a type of graphs which emerged in the past couple of decades under a wealth of names and in various disguises in ...different fields of mathematics and its applications. The central role is played by Sierpiński graphs, but we will also shed some light on variants of these graphs and in particular propose their classification. Concentrating on Sierpiński graphs proper we present results on their metric aspects, domination-type invariants with an emphasis on perfect codes, different colorings, and embeddings into other graphs.
Abstract
The Sierpiński graphs and hierarchical graphs are two much studied self-similar networks, both of which are iteratively constructed and have the same number of vertices and edges at any ...iteration, but display entirely different topological properties. Both graphs have a large variety of applications: Sierpiński graphs have a close connection with WK-recursive networks that are employed extensively in the design and implementation of local area networks and parallel processing architectures, while hierarchical graphs can be used to model complex networks. In this paper, we study hitting times for several absorbing random walks in Sierpiński graphs and hierarchical graphs. For all considered random walks, we determine exact solutions to hitting times for both graphs. The obtained explicit expressions indicate that the hitting times in both graphs behave quite differently. We show that the structural difference of the graphs is responsible for the disparate behaviors of their hitting times.
Let
G
(
V
,
E
) be a connected and undirected graph with
n
-vertex-set
V
and
m
-edge-set
E
. For each
v
∈
V
, let
N
(
v
) = {
u
|
v
∈
V
and(
u
,
v
) ∈
E
}. For a positive integer
k
, a
k
-rainbow ...dominating function of a graph
G
is a function
f
from
V
(
G
) to a
k
-bit Boolean string
f
(
v
) =
f
k
(
v
)
f
k
− 1
(
v
) …
f
1
(
v
), i.e.,
f
i
(
v
) ∈ {0, 1}, 1 ≤
i
≤
k
, such that for any vertex
v
with
f
(
v
) = 0
(
k
)
we have ⋈
u
∈
N
(
v
)
f
(
u
) = 1
(
k
)
, for all
v
∈
V
, where ⋈
u
∈
S
f
(
u
) denotes the result of taking bitwise OR operation on
f
(
u
), for all
u
∈
S
. The weight of
f
is defined as
w
(
f
)
=
∑
v
∈
V
∑
i
=
1
k
f
i
(
v
)
. The
k
-rainbow domination number
γ
k
r
(
G
) is the minimum weight of a
k
-rainbow dominating function over all
k
-rainbow dominating functions of
G
. The 1-rainbow domination is the same as the ordinary domination. The
k
-rainbow domination problem is to determine the
k
-rainbow domination number of a graph
G
. In this paper, we determine
γ
2
r
(
S
(
n
,
m
)),
γ
2
r
(
S
+
(
n
,
m
)), and
γ
2
r
(
S
++
(
n
,
m
)), where
S
(
n
,
m
),
S
+
(
n
,
m
), and
S
++
(
n
,
m
) are Sierpiński graphs and extended Sierpiński graphs.
ON DISTANCES IN GENERALIZED SIERPIŃSKI GRAPHS Estrada-Moreno, Alejandro; Rodríguez-Bazan, Erick D.; Rodríguez-Velázquez, Juan A.
Applicable analysis and discrete mathematics,
04/2018, Letnik:
12, Številka:
1
Journal Article
Recenzirano
Odprti dostop
In this paper we propose formulas for the distance between vertices of a generalized Sierpiński graph 𝑆(𝐺, 𝑡) in terms of the distance between vertices of the base graph 𝐺. In particular, we ...deduce a recursive formula for the distance between an arbitrary vertex and an extreme vertex of 𝑆(𝐺, 𝑡), and we obtain a recursive formula for the distance between two arbitrary vertices of 𝑆(𝐺, 𝑡) when the base graph is triangle-free. From these recursive formulas, we provide algorithms to compute the distance between vertices of 𝑆(𝐺, 𝑡). In addition, we give an explicit formula for the diameter and radius of 𝑆(𝐺, 𝑡) when the base graph is a tree.
Chemical indices of graphs have been studied intensively in the recent years and some generalizations of old indices are very useful in chemical research. In this paper we study Graovac-Pisanski ...index (sometimes known as modified Wiener index) which is denoted by Ŵ. We derive recursive and closed formula for the Graovac-Pisanski index of the classical Sierpiński graphs (i.e., the Sierpiński graphs with base 3, S3n).
If G is a graph, then a sequence v1,…,vm of vertices is a closed neighborhood sequence if for all 2≤i≤m we have Nvi⁄⊆∪j=1i−1Nvj, and it is an open neighborhood sequence if for all 2≤i≤m we have ...N(vi)⁄⊆∪j=1i−1N(vj). The length of a longest closed (open) neighborhood sequence is the Grundy (Grundy total) domination number of G. In this paper we introduce two similar concepts in which the requirement on the neighborhoods is changed to N(vi)⁄⊆∪j=1i−1Nvj or Nvi⁄⊆∪j=1i−1N(vj). In the former case we establish a strong connection to the zero forcing number of a graph, while we determine the complexity of the decision problem in the latter case. We also study the relationships among the four concepts, and discuss their computational complexities.
PDF
