Sierpiński triangle graphs Ŝn have often been mistaken for Sierpiński graphs S3n. Whereas the latter’s metric properties are by now well understood, the former graphs were mostly just considered as ...a pictorial representation of approximations to the Sierpiński triangle fractal. Therefore, we present here a new labeling for them which shows the relation, but also the differences to the more famous Sierpiński graphs proper. On the base of this labeling we describe an algorithm to obtain individual distances between vertices. This type of algorithm can then be extended to base-p Sierpiński triangle graphs Ŝpn which are related to the class of classical Sierpiński graphs Spn, p≥2. Some of the metric properties of Spn can now be investigated for Ŝpn as well; e.g., we characterize center and periphery of Ŝpn.
A map f : V?(0,1,2) is a Roman dominating function on a graph G = (V,E)
if for every vertex v ? V with f(v)=0, there exists a vertex u, adjacent
to v, such that f(u)=2. The weight of a Roman ...dominating function is
given by f(V)=?u?V f(u). The minimum weight among all Roman dominating
functions on G is called the Roman domination number of G. In this article
we study the Roman domination number of Generalized Sierpi?ski graphs
S(G,t). More precisely, we obtain a general upper bound on the Roman
domination number of S(G,t) and discuss the tightness of this bound. In
particular, we focus on the cases in which the base graph G is a path, a
cycle, a complete graph or a graph having exactly one universal vertex.
nema
The median of Sierpiński graphs Balakrishnan, Kannan; Changat, Manoj; Hinz, Andreas M. ...
Discrete Applied Mathematics,
10/2022, Letnik:
319
Journal Article
Recenzirano
The median of a graph consists of those vertices which minimize the average distance to all other vertices. It plays an important role in optimization scenarios like facility location problems. ...Sierpiński graphs are the state graphs of the Switching Tower of Hanoi problem, a variant of the Tower of Hanoi game. They also provide optimum models for interconnection networks. In this study, we present our observations on the median of Sierpiński graphs. We conjecture that the number of median vertices in S3n is always 12, if n≥3, and that they lie around the inner ring of the standard drawing.
The number of spanning trees is an important graph invariant related to different topological and dynamic properties of the graph, such as its reliability, synchronization capability and diffusion ...properties. In 2007, Chang et al. proposed two conjectures on the number of spanning trees of Sierpiński triangle graphs and its spanning tree entropy. In this paper, we completely confirm these conjectures. For data center networks Dk,n, we get the exact formula for k=1, and upper and lower bounds for k≥2. Our results allow also the calculation of the spanning tree entropy of Sierpiński graphs and data center networks.
On Entropy of Some Fractal Structures Ghazwani, Haleemah; Nadeem, Muhammad Faisal; Ishfaq, Faiza ...
Fractal and fractional,
04/2023, Letnik:
7, Številka:
5
Journal Article
Recenzirano
Odprti dostop
Shannon entropy, also known as information entropy or entropy, measures the uncertainty or randomness of probability distribution. Entropy is measured in bits, quantifying the average amount of ...information required to identify an event from the distribution. Shannon’s entropy theory initiates graph entropies and develops information-theoretic magnitudes for structural computational evidence of organic graphs and complex networks. Graph entropy measurements are valuable in several scientific fields, such as computing, chemistry, biology, and discrete mathematics. In this study, we investigate the entropy of fractal-type networks by considering cycle, complete, and star networks as base graphs using degree-based topological indices.
A (d, 1)-total labelling of a simple graph G is an assignment of integers to V(G) ∪ E(G) such that any two adjacent vertices of G receive distinct integers, any two adjacent edges of G receive ...distinct integers, and a vertex and an edge that are incident in G receive integers that differ by at least d in absolute value. The span of a (d, 1)-total labellingof G is the maximum difference between any two labels. The (d, 1)-total number of G, λdT(G), is the minimum span for which G is (d, 1)-total labelled. In this paper, the (d, 1)-total labellingof the Sierpin´ski graph S(n, k), Sierpin´ski gasket graph Sn, graphs S+(n,k) and S++(n,k) are studied, and all of λdT(S(n,k)),λdT(Sn),λdT(S+(n,k)) and λdT(S++(n,k)) for d ≥ k, are obtained.
The minimum dominating set (MDS) problem is a fundamental subject of theoretical computer science, and has found vast applications in different areas, including sensor networks, protein interaction ...networks, and structural controllability. However, the determination of the size of a MDS and the number of all MDSs in a general network is NP-hard, and it thus makes sense to seek particular graphs for which the MDS problem can be solved analytically. In this paper, we study the MDS problem in the pseudofractal scale-free web and the Sierpiński graph, which have the same number of vertices and edges. For both networks, we determine explicitly the domination number, as well as the number of distinct MDSs. We show that the pseudofractal scale-free web has a unique MDS, and its domination number is only half of that for the Sierpiński graph, which has many MDSs. We argue that the scale-free topology is responsible for the difference of the size and number of MDSs between the two studied graphs, which in turn indicates that power-law degree distribution plays an important role in the MDS problem and its applications in scale-free networks.
The General Randić index Rα of a simple graph G is defined as Rα(G)=∑vi∼vjd(vi)d(vj)α,where d(vi) denotes the degree of the vertex vi. Rodríguez-Velázquez and Tomás-Andreu (2015) obtained closed ...formulae for the Randić index R−1∕2 of Sierpiński-type polymeric networks, where the base graph is a complete graph, a triangle-free regular graph or a bipartite semiregular graph. In the present article we obtain closed formulae for the general Randić index Rα of Sierpiński-type polymeric networks, where the base graph is arbitrary.
For a graph G, an infinite series of self-similar graphs is formed by the generalized Sierpiński graphs SGt, t≥1. In the case when G is complete we have the classical Sierpiński graphs Snt=SKnt. In ...this paper the Wiener index, the Wiener complexity, and the metric dimension of their antipode family SK1,nt are determined. Along the way some other properties of the family are also obtained such as the number of vertex and edge orbits of the automorphism group of SK1,nt.
The packing chromatic number
χ
ρ
(
G
)
of a graph
G
is the smallest integer
k
such that the vertex set of
G
can be partitioned into sets
V
i
,
i
∈
{
1
,
…
,
k
}
, where each
V
i
is an
i
-packing. In ...this paper, we consider the packing chromatic number of several families of Sierpiński-type graphs. While it is known that this number is bounded from above by 8 in the family of Sierpiński graphs with base 3, we prove that it is unbounded in the families of Sierpiński graphs with bases greater than 3. On the other hand, we prove that the packing chromatic number in the family of Sierpiński triangle graphs
S
T
3
n
is bounded from above by 31. Furthermore, we establish or provide bounds for the packing chromatic numbers of generalized Sierpiński graphs
S
G
n
with respect to all connected graphs
G
of order 4.
PDF
