{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,9]],"date-time":"2026-07-09T06:34:36Z","timestamp":1783578876622,"version":"3.55.0"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T00:00:00Z","timestamp":1742601600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T00:00:00Z","timestamp":1742601600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100021856","name":"Ministero dell'Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["PRIN Project n. 2022TS4Y3N - EXPAND: scalable algorithms for EXPloratory Analyses of heterogeneous and dynamic Networked Data."],"award-info":[{"award-number":["PRIN Project n. 2022TS4Y3N - EXPAND: scalable algorithms for EXPloratory Analyses of heterogeneous and dynamic Networked Data."]}],"id":[{"id":"10.13039\/501100021856","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Luiss University"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2025,6]]},"abstract":"Abstract<\/jats:title>\n A graph \n \n $$G=(V,E)$$<\/jats:tex-math>\n \n \n G<\/mml:mi>\n =<\/mml:mo>\n (<\/mml:mo>\n V<\/mml:mi>\n ,<\/mml:mo>\n E<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> is a star-k<\/jats:italic>-pairwise compatibility graph (star-k<\/jats:italic>-PCG) if there exists a weight function \n \n $$w: V \\rightarrow \\mathbb {R}^+$$<\/jats:tex-math>\n \n \n w<\/mml:mi>\n :<\/mml:mo>\n V<\/mml:mi>\n \u2192<\/mml:mo>\n \n \n R<\/mml:mi>\n <\/mml:mrow>\n +<\/mml:mo>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> and k<\/jats:italic> mutually exclusive intervals \n \n $$I_1, I_2, \\ldots I_k$$<\/jats:tex-math>\n \n \n \n I<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \n I<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \u2026<\/mml:mo>\n \n I<\/mml:mi>\n k<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, such that there is an edge \n \n $$uv \\in E$$<\/jats:tex-math>\n \n \n u<\/mml:mi>\n v<\/mml:mi>\n \u2208<\/mml:mo>\n E<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> if and only if \n \n $$w(u)+w(v) \\in \\bigcup _i I_i$$<\/jats:tex-math>\n \n \n w<\/mml:mi>\n \n (<\/mml:mo>\n u<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n +<\/mml:mo>\n w<\/mml:mi>\n \n (<\/mml:mo>\n v<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \u2208<\/mml:mo>\n \n \u22c3<\/mml:mo>\n i<\/mml:mi>\n <\/mml:msub>\n \n I<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>. These graphs are related to two important classes of graphs: pairwise compatibility graphs (PCGs) and multithreshold graphs. It is known that for any graph G<\/jats:italic> there exists a k<\/jats:italic> such that G<\/jats:italic> is a star-k<\/jats:italic>-PCG. Thus, for a given graph G<\/jats:italic> it is interesting to know which is the minimum k<\/jats:italic> such that G<\/jats:italic> is a star-k<\/jats:italic>-PCG. We define this minimum k<\/jats:italic> as the star number<\/jats:italic> of the graph, denoted by \n \n $$\\gamma (G)$$<\/jats:tex-math>\n \n \n \u03b3<\/mml:mi>\n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>. Here we investigate the star number of simple graph classes, such as graphs of small size, caterpillars, cycles and grids. Specifically, we determine the exact value of \n \n $$\\gamma (G)$$<\/jats:tex-math>\n \n \n \u03b3<\/mml:mi>\n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> for all the graphs with at most 7 vertices. By doing so we show that the smallest graphs with star number 2 are only 4 and have exactly 5 vertices; the smallest graphs with star number 3 are only 3 and have exactly 7 vertices. Next, we provide a construction showing that the star number of caterpillars is one. Moreover, we show that the star number of cycles and two-dimensional grid graphs is 2 and that the star number of 4-dimensional grids is at least 3. Finally, we conclude with numerous open problems.<\/jats:p>","DOI":"10.1007\/s00236-025-00485-z","type":"journal-article","created":{"date-parts":[[2025,3,23]],"date-time":"2025-03-23T09:19:28Z","timestamp":1742721568000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On star-k-PCGs: exploring class boundaries for small k values"],"prefix":"10.1007","volume":"62","author":[{"given":"Angelo","family":"Monti","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Blerina","family":"Sinaimeri","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,3,22]]},"reference":[{"key":"485_CR1","doi-asserted-by":"publisher","unstructured":"Monti, A., Sinaimeri, B.: On star-multi-interval pairwise compatibility graphs. In: WALCOM: Algorithms and Computation: 17th International Conference and Workshops, WALCOM 2023, Hsinchu, Taiwan, March 22-24, 2023, Proceedings, pp. 267\u2013278. Springer, Berlin, Heidelberg (2023). https:\/\/doi.org\/10.1007\/978-3-031-27051-2_23","DOI":"10.1007\/978-3-031-27051-2_23"},{"key":"485_CR2","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/978-3-319-55911-7_6","volume-title":"Theory and Applications of Models of Computation","author":"S Ahmed","year":"2017","unstructured":"Ahmed, S., Rahman, M.S.: Multi-interval pairwise compatibility graphs. In: Gopal, T.V., J\u00e4ger, G., Steila, S. (eds.) Theory and Applications of Models of Computation, pp. 71\u201384. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-55911-7_6"},{"key":"485_CR3","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/978-3-540-39763-2_14","volume-title":"Algorithms in Bioinformatics","author":"P Kearney","year":"2003","unstructured":"Kearney, P., Munro, J.I., Phillips, D.: Efficient generation of uniform samples from phylogenetic trees. In: Benson, G., Page, R.D.M. (eds.) Algorithms in Bioinformatics, pp. 177\u2013189. Springer, Berlin, Heidelberg (2003). https:\/\/doi.org\/10.1007\/978-3-540-39763-2_14"},{"issue":"1","key":"485_CR4","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1006\/jagm.2001.1195","volume":"42","author":"N Nishimura","year":"2002","unstructured":"Nishimura, N., Ragde, P., Thilikos, D.M.: On graph powers for leaf-labeled trees. J. Algorithms 42(1), 69\u2013108 (2002). https:\/\/doi.org\/10.1006\/jagm.2001.1195","journal-title":"J. Algorithms"},{"key":"485_CR5","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1016\/j.dam.2020.05.015","volume":"285","author":"Y Long","year":"2020","unstructured":"Long, Y., Stadler, P.F.: Exact-2-relation graphs. Discrete Appl. Math. 285, 212\u2013226 (2020). https:\/\/doi.org\/10.1016\/j.dam.2020.05.015","journal-title":"Discrete Appl. Math."},{"key":"485_CR6","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1007\/978-3-540-78773-0_42","volume-title":"Ptolemaic Graphs and Interval Graphs Are Leaf Powers","author":"A Brandst\u00e4dt","year":"2008","unstructured":"Brandst\u00e4dt, A., Hundt, C.: Ptolemaic Graphs and Interval Graphs Are Leaf Powers, pp. 479\u2013491. Springer, Berlin (2008). https:\/\/doi.org\/10.1007\/978-3-540-78773-0_42"},{"key":"485_CR7","doi-asserted-by":"publisher","DOI":"10.1142\/s1793830913600021","author":"T Calamoneri","year":"2013","unstructured":"Calamoneri, T., Petreschi, R., Sinaimeri, B.: On the pairwise compatibility property of some superclasses of threshold graphs. Discrete Math. Algorithms Appl. (2013). https:\/\/doi.org\/10.1142\/s1793830913600021","journal-title":"Discrete Math. Algorithms Appl."},{"key":"485_CR8","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1007\/978-3-031-15914-5_6","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"B Benjamin","year":"2022","unstructured":"Benjamin, B., H\u00f8gemo, S., Telle, J.A., Vatshelle, M.: Recognition of linear and star variants of leaf powers is in P. In: Bekos, M.A., Kaufmann, M. (eds.) Graph-Theoretic Concepts in Computer Science, pp. 70\u201383. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-15914-5_6"},{"key":"485_CR9","unstructured":"Monti, A., Sinaimeri, B.: On graphs that are not Star-k-PCGs (short paper). In: Castiglione, G., Sciortino, M. (eds.) Proceedings of the 24th Italian Conference on Theoretical Computer Science, Palermo, Italy, September 13-15, 2023. CEUR Workshop Proceedings, vol. 3587, pp. 92\u201397. CEUR-WS.org, Aachen, Germany (2023). https:\/\/ceur-ws.org\/Vol-3587\/0910.pdf"},{"issue":"10","key":"485_CR10","doi-asserted-by":"publisher","first-page":"3066","DOI":"10.1007\/s00453-020-00712-8","volume":"82","author":"M Xiao","year":"2020","unstructured":"Xiao, M., Nagamochi, H.: Characterizing Star-PCGs. Algorithmica 82(10), 3066\u20133090 (2020). https:\/\/doi.org\/10.1007\/s00453-020-00712-8","journal-title":"Algorithmica"},{"issue":"4","key":"485_CR11","doi-asserted-by":"publisher","first-page":"1163","DOI":"10.1007\/s00453-021-00921-9","volume":"84","author":"Y Kobayashi","year":"2022","unstructured":"Kobayashi, Y., Okamoto, Y., Otachi, Y., Uno, Y.: Linear-time recognition of double-threshold graphs. Algorithmica 84(4), 1163\u20131181 (2022). https:\/\/doi.org\/10.1007\/s00453-021-00921-9","journal-title":"Algorithmica"},{"key":"485_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/s10801-021-01029-7","author":"RE Jamison","year":"2021","unstructured":"Jamison, R.E., Sprague, A.P.: Double-threshold permutation graphs. J. Algebraic Comb. (2021). https:\/\/doi.org\/10.1007\/s10801-021-01029-7","journal-title":"J. Algebraic Comb."},{"key":"485_CR13","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/S0167-5060(08)70731-3","volume":"1","author":"V Chv\u00e1tal","year":"1977","unstructured":"Chv\u00e1tal, V., Hammer, P.L.: Aggregation of inequalities in integer programming. Ann. Discrete Math. 1, 145\u2013162 (1977). https:\/\/doi.org\/10.1016\/S0167-5060(08)70731-3","journal-title":"Ann. Discrete Math."},{"key":"485_CR14","series-title":"Annals of Discrete Mathematics","volume-title":"Threshold Graphs and Related Topics","author":"NVR Mahadev","year":"1995","unstructured":"Mahadev, N.V.R.: Threshold Graphs and Related Topics. Annals of Discrete Mathematics, vol. 543. Elsevier, Amsterdam, New York (1995)"},{"issue":"3","key":"485_CR15","doi-asserted-by":"publisher","first-page":"913","DOI":"10.1007\/s00373-020-02168-7","volume":"36","author":"GJ Puleo","year":"2020","unstructured":"Puleo, G.J.: Some results on multithreshold graphs. Gr. Comb. 36(3), 913\u2013919 (2020). https:\/\/doi.org\/10.1007\/s00373-020-02168-7","journal-title":"Gr. Comb."},{"key":"485_CR16","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22805","author":"G Chen","year":"2022","unstructured":"Chen, G., Hao, Y.: Multithreshold multipartite graphs. J. Gr. Theory (2022). https:\/\/doi.org\/10.1002\/jgt.22805","journal-title":"J. Gr. Theory"},{"issue":"7","key":"485_CR17","doi-asserted-by":"publisher","first-page":"882","DOI":"10.1093\/comjnl\/bxs087","volume":"56","author":"T Calamoneri","year":"2012","unstructured":"Calamoneri, T., Frascaria, D., Sinaimeri, B.: All graphs with at most seven vertices are pairwise compatibility graphs. Comput. J. 56(7), 882\u2013886 (2012). https:\/\/doi.org\/10.1093\/comjnl\/bxs087","journal-title":"Comput. J."},{"key":"485_CR18","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1016\/j.tcs.2015.01.011","volume":"571","author":"S Durocher","year":"2015","unstructured":"Durocher, S., Mondal, D., Rahman, M.S.: On graphs that are not PCGs. Theor. Comput. Sci. 571, 78\u201387 (2015). https:\/\/doi.org\/10.1016\/j.tcs.2015.01.011","journal-title":"Theor. Comput. Sci."},{"key":"485_CR19","doi-asserted-by":"publisher","unstructured":"Calamoneri, T., Monti, A., Petroni, F.: All Graphs with at most 8 nodes are 2-interval-PCGs. arXiv (2022). https:\/\/doi.org\/10.48550\/ARXIV.2202.13844","DOI":"10.48550\/ARXIV.2202.13844"},{"issue":"4","key":"485_CR20","doi-asserted-by":"publisher","first-page":"518","DOI":"10.1002\/jgt.22541","volume":"94","author":"RE Jamison","year":"2020","unstructured":"Jamison, R.E., Sprague, A.P.: Multithreshold graphs. J. Gr. Theory 94(4), 518\u2013530 (2020). https:\/\/doi.org\/10.1002\/jgt.22541","journal-title":"J. Gr. Theory"},{"key":"485_CR21","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1007\/s12190-008-0204-7","volume":"30","author":"MN Yanhaona","year":"2009","unstructured":"Yanhaona, M.N., Hossain, K.S.M.T., Rahman, M.S.: Pairwise compatibility graphs. J. Appl. Math. Comput. 30, 479\u2013503 (2009). https:\/\/doi.org\/10.1007\/s12190-008-0204-7","journal-title":"J. Appl. Math. Comput."},{"key":"485_CR22","doi-asserted-by":"publisher","first-page":"106284","DOI":"10.1016\/j.ipl.2022.106284","volume":"178","author":"SA Hakim","year":"2022","unstructured":"Hakim, S.A., Papan, B.B., Rahman, M.S.: New results on pairwise compatibility graphs. Inf. Process. Lett. 178, 106284 (2022). https:\/\/doi.org\/10.1016\/j.ipl.2022.106284","journal-title":"Inf. Process. Lett."},{"key":"485_CR23","unstructured":"OEIS Foundation Inc.: Number of graphs on n unlabeled nodes. Entry A000088, The On-Line Encyclopedia of Integer Sequences. https:\/\/oeis.org\/A000088 (n.b.)"},{"key":"485_CR24","unstructured":"https:\/\/github.com\/sinaimeri\/star-k-PCGs (2024)"},{"key":"485_CR25","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxac011","author":"BB Papan","year":"2022","unstructured":"Papan, B.B., Pranto, P.B., Rahman, M.S.: On 2-interval pairwise compatibility properties of two classes of grid graphs. Comput. J. (2022). https:\/\/doi.org\/10.1093\/comjnl\/bxac011","journal-title":"Comput. J."},{"issue":"2","key":"485_CR26","doi-asserted-by":"publisher","first-page":"81","DOI":"10.7155\/jgaa.00286","volume":"17","author":"S Salma","year":"2013","unstructured":"Salma, S., Rahman, M., Hossain, M.: Triangle-free outerplanar 3-graphs are pairwise compatibility graphs. J. Gr. Algorithms Appl. 17(2), 81\u2013102 (2013). https:\/\/doi.org\/10.7155\/jgaa.00286","journal-title":"J. Gr. Algorithms Appl."}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-025-00485-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-025-00485-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-025-00485-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T11:42:32Z","timestamp":1750160552000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-025-00485-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,22]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["485"],"URL":"https:\/\/doi.org\/10.1007\/s00236-025-00485-z","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,3,22]]},"assertion":[{"value":"10 February 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 March 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 March 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"17"}}