Recognizing generalized Sierpiński graphs
Publikationen: Beitrag in Fachzeitschrift › Artikel › Forschung › (peer-reviewed)
Autoren
Organisationseinheiten
Externe Organisationseinheiten
- Universität Maribor
Abstract
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 .
Details
Originalsprache | Englisch |
---|---|
Seiten (von - bis) | 122-137 |
Seitenumfang | 16 |
Fachzeitschrift | Applicable analysis and discrete mathematics |
Jahrgang | 14.2020 |
Ausgabenummer | 1 |
DOIs | |
Status | Veröffentlicht - 1 Apr. 2020 |