Recognizing generalized Sierpiński graphs
Research output: Contribution to journal › Article › Research › peer-review
Standard
In: Applicable analysis and discrete mathematics, Vol. 14.2020, No. 1, 01.04.2020, p. 122-137.
Research output: Contribution to journal › Article › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex - Download
}
RIS (suitable for import to EndNote) - Download
TY - JOUR
T1 - Recognizing generalized Sierpiński graphs
AU - Imrich, Wilfried
AU - Peterin, Iztok
PY - 2020/4/1
Y1 - 2020/4/1
N2 - Let H be an arbitrary graph with vertex set V (H) = [nH] = {l,…, nH}. The generalized Sierpiński graph SnH , n ∈ N, is defined on the vertex set [nH]n, two different vertices u = un …u1 and v = vn … v1 being adjacent if there exists an h∈ [n] such that (a) ut = vt, for t > h, (b) uh ≠ vh and uhvh ∈ E(H), and (c) ut = vh and vt = uh for t < h. If H is the complete graph Kk, then we speak of the Sierpiński graph Sn k . We present an algorithm that recognizes Sierpiński graphs Sn k in O(|V (Sn k )|1+1=n) = O(|E(Sn k )|) time. For generalized Sierpiński graphs SnH 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 SnH .
AB - Let H be an arbitrary graph with vertex set V (H) = [nH] = {l,…, nH}. The generalized Sierpiński graph SnH , n ∈ N, is defined on the vertex set [nH]n, two different vertices u = un …u1 and v = vn … v1 being adjacent if there exists an h∈ [n] such that (a) ut = vt, for t > h, (b) uh ≠ vh and uhvh ∈ E(H), and (c) ut = vh and vt = uh for t < h. If H is the complete graph Kk, then we speak of the Sierpiński graph Sn k . We present an algorithm that recognizes Sierpiński graphs Sn k in O(|V (Sn k )|1+1=n) = O(|E(Sn k )|) time. For generalized Sierpiński graphs SnH 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 SnH .
KW - Algorithm
KW - Generalized sierpiński graphs
KW - Sierpiński graphs
UR - http://www.scopus.com/inward/record.url?scp=85092225064&partnerID=8YFLogxK
U2 - 10.2298/AADM180331003I
DO - 10.2298/AADM180331003I
M3 - Article
AN - SCOPUS:85092225064
VL - 14.2020
SP - 122
EP - 137
JO - Applicable analysis and discrete mathematics
JF - Applicable analysis and discrete mathematics
SN - 1452-8630
IS - 1
ER -
