Back to Search
Start Over
RECOGNIZING GENERALIZED SIERPIŃSKI GRAPHS.
- Source :
-
Applicable Analysis & Discrete Mathematics . Apr2020, Vol. 14 Issue 1, p122-137. 16p. - Publication Year :
- 2020
-
Abstract
- Let H be an arbitrary graph with vertex set V (H) = [nH] = {1, ...,nH}. The generalized Sierpiriski graph SHn, 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 e [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 Skn. We present an algorithm that recognizes Sierpiński graphs Skn in O(|V(Sn )|1+1/n) = O(|E(Skn)|) time. For generalized Sierpiński graphs SH 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 SHn. [ABSTRACT FROM AUTHOR]
- Subjects :
- *POLYNOMIAL time algorithms
*ALGORITHMS
*COMPLETE graphs
Subjects
Details
- Language :
- English
- ISSN :
- 14528630
- Volume :
- 14
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- Applicable Analysis & Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 146124129
- Full Text :
- https://doi.org/10.2298/AADM180331003I