{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,14]],"date-time":"2025-05-14T02:30:03Z","timestamp":1747189803758,"version":"3.40.5"},"reference-count":56,"publisher":"World Scientific Pub Co Pte Ltd","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2021,2]]},"abstract":"<jats:p> For any finite simple undirected graph [Formula: see text], we consider the binary relation [Formula: see text] on the powerset [Formula: see text] of its vertex set given by [Formula: see text] if [Formula: see text], where [Formula: see text] denotes the neighborhood of a vertex [Formula: see text]. We call the above relation set adiacence dependency (sa)-dependency of [Formula: see text]. With the relation [Formula: see text] we associate an intersection-closed family [Formula: see text] of vertex subsets and the corresponding induced lattice [Formula: see text], which we call sa-lattice of [Formula: see text]. Through the equality of sa-lattices, we introduce an equivalence relation [Formula: see text] between graphs and propose three different classifications of graphs based on such a relation. Furthermore, we determine the sa-lattice for various graph families, such as complete graphs, complete bipartite graphs, cycles and paths and, next, we study such a lattice in relation to the Cartesian and the tensor product of graphs, verifying that in most cases it is a graded lattice. Finally, we provide two algorithms, namely, the T-DI ALGORITHM and the O-F ALGORITHM, in order to provide two different computational ways to construct the sa-lattice of a graph. For the O-F ALGORITHM we also determine its computational complexity. <\/jats:p>","DOI":"10.1142\/s1793830920500895","type":"journal-article","created":{"date-parts":[[2020,7,13]],"date-time":"2020-07-13T13:01:31Z","timestamp":1594645291000},"page":"2050089","source":"Crossref","is-referenced-by-count":0,"title":["Some classifications of graphs with respect to a set adjacency relation"],"prefix":"10.1142","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2247-2386","authenticated-orcid":false,"given":"G.","family":"Chiaselotti","sequence":"first","affiliation":[{"name":"Department of Mathematics and Computer Science, University of Calabria, Via Pietro Bucci Cubo 30B, 87036 Arcavacata di Rende (CS), Italy"}]},{"given":"T.","family":"Gentile","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science, University of Calabria, Via Pietro Bucci Cubo 30B, 87036 Arcavacata di Rende (CS), Italy"}]},{"given":"F. G.","family":"Infusino","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science, University of Calabria, Via Pietro Bucci Cubo 30B, 87036 Arcavacata di Rende (CS), Italy"}]}],"member":"219","published-online":{"date-parts":[[2020,9,21]]},"reference":[{"key":"S1793830920500895BIB001","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/j.ins.2017.05.002","volume":"409","author":"Aledo J. A.","year":"2017","journal-title":"Inf. Sci."},{"journal-title":"J. Comp. Appl. Math.","year":"2018","author":"Aledo J. A.","key":"S1793830920500895BIB002"},{"issue":"4","key":"S1793830920500895BIB003","first-page":"1803","volume":"9","author":"Aledo J. A.","year":"2015","journal-title":"Appl. Math. Inf. Sci."},{"issue":"1","key":"S1793830920500895BIB004","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/0095-8956(73)90027-0","volume":"15","author":"Alspach B.","year":"1973","journal-title":"J. Combin. Th., Ser. B"},{"key":"S1793830920500895BIB005","first-page":"1","volume-title":"Graph Symmetry","author":"Alspach B.","year":"1997"},{"key":"S1793830920500895BIB006","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1017\/S1446788700012313","volume":"28","author":"Alspach B.","year":"1979","journal-title":"J. Austr. Math. Soc. Ser. A"},{"issue":"2","key":"S1793830920500895BIB007","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/0012-365X(84)90062-1","volume":"49","author":"Batten L. M.","year":"1984","journal-title":"Discr. Math."},{"key":"S1793830920500895BIB008","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511666919","volume-title":"The Theory of Finite Linear Spaces-Ccombinatorics of Points and Lines","author":"Batten L. M.","year":"1993"},{"issue":"4","key":"S1793830920500895BIB009","doi-asserted-by":"crossref","first-page":"446","DOI":"10.1137\/S0895480100338002","volume":"14","author":"Batten L. M.","year":"2001","journal-title":"SIAM J. Discr. Math."},{"issue":"2","key":"S1793830920500895BIB010","first-page":"1750027","volume":"9","author":"Behtoei A.","year":"2017","journal-title":"Discr. Math. Alg. Appl."},{"key":"S1793830920500895BIB011","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.dam.2015.02.023","volume":"188","author":"Berend D.","year":"2015","journal-title":"Discr. Appl. Math."},{"volume-title":"Hypergraphs: Combinatorics of Finite Sets","year":"1984","author":"Berge C.","key":"S1793830920500895BIB012"},{"key":"S1793830920500895BIB013","volume-title":"Lattice Theory","author":"Birkhoff G.","year":"1967","edition":"3"},{"issue":"4","key":"S1793830920500895BIB014","doi-asserted-by":"crossref","first-page":"875","DOI":"10.1007\/s00209-007-0203-7","volume":"258","author":"Bisi C.","year":"2008","journal-title":"Math. Zeit."},{"issue":"1","key":"S1793830920500895BIB015","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1016\/j.jmaa.2008.09.023","volume":"350","author":"Bisi C.","year":"2009","journal-title":"J. Math. An. Appl."},{"issue":"2","key":"S1793830920500895BIB016","doi-asserted-by":"crossref","first-page":"737","DOI":"10.1007\/s10231-016-0593-4","volume":"196","author":"Bisi C.","year":"2017","journal-title":"Ann. Mat. Pur. Appl."},{"issue":"4","key":"S1793830920500895BIB017","doi-asserted-by":"crossref","first-page":"1291","DOI":"10.1016\/j.disc.2015.11.014","volume":"339","author":"Bonacini P.","year":"2016","journal-title":"Discr. Math."},{"issue":"6","key":"S1793830920500895BIB018","doi-asserted-by":"crossref","first-page":"1265","DOI":"10.11650\/tjm\/8042","volume":"21","author":"Bujt\u00e1s C.","year":"2017","journal-title":"Taiw. J. Math."},{"journal-title":"Inf. Sci.","year":"2020","author":"Catanzariti F.","key":"S1793830920500895BIB019"},{"key":"S1793830920500895BIB020","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/j.ejc.2016.02.003","volume":"55","author":"Cattaneo G.","year":"2016","journal-title":"Eur. J. Combin."},{"key":"S1793830920500895BIB021","doi-asserted-by":"crossref","first-page":"R16","DOI":"10.37236\/934","volume":"14","author":"Charon I.","year":"2007","journal-title":"Elec. J. Combin."},{"key":"S1793830920500895BIB022","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/j.ins.2016.08.037","volume":"373","author":"Chiaselotti G.","year":"2016","journal-title":"Inf. Sci."},{"key":"S1793830920500895BIB023","doi-asserted-by":"crossref","first-page":"3171","DOI":"10.1016\/j.disc.2016.07.003","volume":"340","author":"Chiaselotti G.","year":"2017","journal-title":"Discr. Math."},{"key":"S1793830920500895BIB024","doi-asserted-by":"crossref","first-page":"991","DOI":"10.1016\/j.crma.2017.09.010","volume":"355","author":"Chiaselotti G.","year":"2017","journal-title":"C. R. Acad. Sci. Paris, Ser. I"},{"key":"S1793830920500895BIB025","doi-asserted-by":"publisher","DOI":"10.1142\/S021949881950004X"},{"issue":"3","key":"S1793830920500895BIB026","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1017\/S1446788718000137","volume":"106","author":"Chiaselotti G.","year":"2019","journal-title":"J. Austr. Math. Soc."},{"key":"S1793830920500895BIB027","doi-asserted-by":"publisher","DOI":"10.1142\/S0218196719500607"},{"issue":"1","key":"S1793830920500895BIB028","doi-asserted-by":"crossref","first-page":"P1.19","DOI":"10.37236\/8786","volume":"27","author":"Chiaselotti G.","year":"2020","journal-title":"Elec. J. Combin."},{"issue":"3","key":"S1793830920500895BIB029","doi-asserted-by":"crossref","first-page":"1073","DOI":"10.1007\/s10231-016-0608-1","volume":"196","author":"Chiaselotti G.","year":"2017","journal-title":"Ann. Mat. Pur. Appl."},{"issue":"5","key":"S1793830920500895BIB030","first-page":"1850063","volume":"10","author":"Chiaselotti G.","year":"2018","journal-title":"Discr. Math. Alg. Appl."},{"issue":"3","key":"S1793830920500895BIB031","doi-asserted-by":"crossref","first-page":"795","DOI":"10.1515\/forum-2019-0283","volume":"32","author":"Chiaselotti G.","year":"2020","journal-title":"Forum Math."},{"key":"S1793830920500895BIB032","doi-asserted-by":"crossref","first-page":"106999","DOI":"10.1016\/j.aim.2020.106999","volume":"363","author":"Chiaselotti G.","year":"2020","journal-title":"Adv. Math."},{"key":"S1793830920500895BIB033","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511809088","volume-title":"Introduction to Lattices and Order","author":"Davey B. A.","year":"2002","edition":"2"},{"key":"S1793830920500895BIB034","doi-asserted-by":"crossref","first-page":"869","DOI":"10.1007\/s00373-017-1810-7","volume":"33","author":"Diao K.","year":"2017","journal-title":"Graphs Combin."},{"key":"S1793830920500895BIB035","series-title":"Graduate Text in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-14279-6","volume-title":"Graph Theory","author":"Diestel R.","year":"2010","edition":"4"},{"key":"S1793830920500895BIB036","doi-asserted-by":"crossref","first-page":"1776","DOI":"10.1016\/j.jmaa.2016.09.069","volume":"446","author":"Doust I.","year":"2017","journal-title":"J. Math. An. Appl."},{"issue":"9","key":"S1793830920500895BIB037","doi-asserted-by":"crossref","first-page":"2336","DOI":"10.1016\/j.jfa.2008.01.013","volume":"254","author":"Doust I.","year":"2008","journal-title":"J. Funct. Anal."},{"issue":"3","key":"S1793830920500895BIB038","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1007\/BF01895716","volume":"14","author":"Erd\u00f6s P.","year":"1963","journal-title":"Acta Math. Hung."},{"key":"S1793830920500895BIB039","doi-asserted-by":"crossref","first-page":"225","DOI":"10.2298\/AADM130827019G","volume":"7","author":"Gionfriddo M.","year":"2013","journal-title":"Applic. Anal. Discr. Math."},{"issue":"1","key":"S1793830920500895BIB040","doi-asserted-by":"crossref","first-page":"163","DOI":"10.2478\/AMNS.2019.1.00016","volume":"4","author":"Goyal S.","year":"2019","journal-title":"Appl. Math. Nonlinear Sci."},{"issue":"1","key":"S1793830920500895BIB041","first-page":"100","volume":"8","author":"Goyal S.","year":"2020","journal-title":"Elec. J. Math. Anal. Appl."},{"key":"S1793830920500895BIB042","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1016\/S0166-218X(97)00091-7","volume":"80","author":"Gravier S.","year":"1997","journal-title":"Discr. Appl. Math."},{"key":"S1793830920500895BIB043","doi-asserted-by":"crossref","first-page":"2408","DOI":"10.1016\/j.dam.2012.06.012","volume":"160","author":"Hu F.","year":"2012","journal-title":"Discr. Appl. Math."},{"key":"S1793830920500895BIB044","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/j.dam.2004.01.019","volume":"145","author":"Jha P. K.","year":"2005","journal-title":"Discr. Appl. Math."},{"issue":"2","key":"S1793830920500895BIB045","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1007\/s003730200023","volume":"18","author":"Jiang T.","year":"2002","journal-title":"Graphs Combin."},{"key":"S1793830920500895BIB046","first-page":"137","volume":"283","author":"Kuo D.","year":"2004","journal-title":"Discr. Appl. Math."},{"issue":"2","key":"S1793830920500895BIB047","first-page":"1650020","volume":"8","author":"Ma X.","year":"2016","journal-title":"Discr. Math. Alg. Appl."},{"issue":"6","key":"S1793830920500895BIB049","first-page":"809","volume":"16","author":"Mishra V. N.","year":"2018","journal-title":"Int. J. Anal. Appl."},{"issue":"1","key":"S1793830920500895BIB050","first-page":"5","volume":"7","author":"Mishra V. N.","year":"2019","journal-title":"Elec. J. Math. Anal. Appl."},{"volume-title":"Rough Sets-Theoretical Aspects of Reasoning About Data","year":"1991","author":"Pawlak Z.","key":"S1793830920500895BIB051"},{"issue":"3","key":"S1793830920500895BIB052","first-page":"1139","volume":"9","author":"Sanahuja S. M.","year":"2015","journal-title":"Appl. Math. Inf. Sci."},{"key":"S1793830920500895BIB053","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1016\/j.amc.2015.11.052","volume":"276","author":"Sanahuja S. M.","year":"2016","journal-title":"Appl. Math. Comp."},{"issue":"4","key":"S1793830920500895BIB054","first-page":"1750048","volume":"7","author":"Si X.","year":"2017","journal-title":"Discr. Math. Alg. Appl."},{"key":"S1793830920500895BIB055","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4471-6407-4","volume-title":"Mathematical Tools for Data Mining","author":"Simovici D. A.","year":"2014"},{"volume-title":"Coloring Mixed Hypergraphs: Theory, Algorithms and Applications","year":"2002","author":"Voloshin V.","key":"S1793830920500895BIB056"},{"key":"S1793830920500895BIB057","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1006\/jmaa.1995.1174","volume":"192","author":"Weston A.","year":"1995","journal-title":"J. Math. An. Appl."}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830920500895","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,19]],"date-time":"2021-01-19T11:00:25Z","timestamp":1611054025000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830920500895"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,21]]},"references-count":56,"journal-issue":{"issue":"01","published-print":{"date-parts":[[2021,2]]}},"alternative-id":["10.1142\/S1793830920500895"],"URL":"https:\/\/doi.org\/10.1142\/s1793830920500895","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"type":"print","value":"1793-8309"},{"type":"electronic","value":"1793-8317"}],"subject":[],"published":{"date-parts":[[2020,9,21]]}}}