A graph is a star--PCG if there exists a non-negative edge weighted star tree and mutually exclusive intervals 1, 2, . . . , of non-negative reals such that each vertex of corresponds to a leaf of and there is an edge between two vertices in if the distance between their corresponding leaves in lies in 1 ∪ 2 ∪ . . . ∪ . These graphs are related to diferent well-studied classes of graphs such as PCGs and multithreshold graphs. In this paper, we investigate the smallest value of such that there exists an vertex graph that is not a star--PCG, for small values of .
Thus, the class of star--PCGs is particularly interesting as it serves as link between two significant graph classes: PCGs and multithreshold graphs, both of which currently lack a complete characterization. Indeed, the computational complexity of determining the minimum value of for a graph to be a -PCG remains an open question, and it is unknown whether this problem can be solved in polynomial time, even for the case of = 1. Nevertheless, recent advancements have been made towards the recognition of star--PCGs. Recently, Xiao and Nagamochi [9] introduced the first polynomial-time algorithm for identifying graphs that are star-1-PCGs. Next, Kobayashi et al. in [10] improved upon this results by introducing a new characterization of star-1-PCGs that led a linear time algorithm for their recognition.
It is already established that every graph is a star--PCG for some positive integer ≤
|()| [
In this paper we ask a similar question for star--PCGs. We show that the smallest graph that is not a star-1-PCG has exactly 5 vertices. Moreover, we fully determine the membership to the star--PCG class for each graph with at most 5 vertices. We conclude with some open questions.
For a graph = (, ) and a vertex ∈ , the set () = { : {, } ∈ } is called the neighborhood of .
Let be an edge weighted star tree for each leaf of we denote by () = the weight of the edge incident to . For a graph , the weighted star tree of is a star whose leaves are the vertices of .
It is already known that every graph is a star--PCG for some positive integer [
Definition 1. Given a graph , we define the star number, (), to be the smallest positive integer , such that is a star--PCG.
From [
In the forthcoming proofs we will use the following results.
Lemma 1. [
Lemma 2. Let be a star--PCG and let be a weighted witness star for . If there are two leaves , in for which () = () then () = ().
There are 34 non isomorphic graphs with 5 vertices [14]. These graphs are depicted in Fig. 2 based on increasing number of edges (see also [15]). Let 5 = {1, 2, . . . , 34} be the set of all non isomorphic graphs with 5 vertices. In this section we show that these graphs are star-1-PCGs or star-2-PCGs. For the sake of simplicity in the forthcoming constructions we will omit to present the star tree proving the membership to star--PCG. Instead, for each leaf vertex in a witness star tree , we will simply associate the weight () to the vertex in the graph . We will refer to this representation as the witness graph. In Fig. 2 we show for each graph ∈ 5 its witness graph together with the corresponding interval(s) proving the membership to star-1-PCG or star-2-PCG. To fully determine the membership to star-1-PCG or star-2-PCG classes, we need the following lemmas.
Lemma 3. (20) = 2 Lemma 4. (25) = (27) = 2.
Proof. Due to space limits we will only detail the proof for the graph 25. Let (25) = {, , , , } as shown in Fig. 2. Assume on the contrary that 25 is a star-1-PCG and let and = [, ] be the witness star tree and the corresponding interval. Notice that from Lemma 2, all the vertices are associate to a diferent weight in . Let 1 = min{(), ()} and 2 = min{(), ()}. Due to the symmetry of the graph, we can assume without loss of generality that 1 = (), 2 = () and () < (). Now, we focus on the weight of vertex relative to the weight of the vertices and . We need to consider the following three cases. • We have () < () < (). Then the following holds:
≤ () + () < () + () < () + () ≤ .
Where the first and last inequalities follow as the edges {, }, {, } belong to (25).
We reach a contradiction as () + () ∈ but , ̸∈ (25). • We have () < () < (). Then the following holds:
≤ () + () < () + () < () + () ≤ .
Where the first and last inequalities follow as the edges {, }, {, } belong to (25).
We reach a contradiction as () + () ∈ but , ̸∈ (25). • We have () < () < (). Then the following holds:
≤ () + () < () + () < () + () ≤ .
Where the first and last inequalities follow as the edges {, }, {, } belong to (25).
We reach a contradiction as () + () ∈ but , ̸∈ (25).
We thus, showed that 25 is not a star-1-PCG. The result for the graph 27 follows in a case by case analysis. .
Theorem 1. All graphs with at most 5 vertices are star-1-PCGs, except for the graphs {15, 20, 25, 27} which are star-2-PCGs.
Proof. For graphs with exactly 5 vertices the proof follows directly by Lemma 3 and Lemma 4
and by noticing that for the graph 15, a cycle on five vertices, (15) = 2 [
Notice that if a graph is a star--PCG, removing a vertex from the graph will still result in a graph that belongs to the class of star--PCGs. A graph with 4 vertices can be viewed as a graph with 5 vertices with one isolated vertex. These graphs are depicted in Fig. 2 and are namely, 1 − 8, 13, 14, 18, 24, which are shown to be star-1-PCGs. The graphs with at most 3 vertices are obtained from the ones of 4 vertices by removing vertices and thus are clearly star-1-PCGs.
In this paper we consider star-multi-interval pairwise compatibility graphs. We show that the smallest graph that is not a star-1-PCG has exactly 5 vertices. Moreover, we fully determine the membership to the star--PCG class for each graph with at most 5 vertices. Many problems remain open.
From the results in this paper we know that this number is at least 6. From the results in [8] we have that 34, the graph consisting of 3 disjoint cliques on four vertices is a star-3-PCG. We conjecture that the smallest graph that is not a star-2-PCG has indeed 12 nodes, and all the graphs with at most 11 nodes are star-2-PCGs. [5] R. Jamison, A. Sprague, Multithreshold graphs., J. Graph Theory 94 (2020) 518–530. [6] G. J. Puleo, Some results on multithreshold graphs, Graphs and Combinatorics 36 (2020) 913–919. doi:10.1007/s00373-020-02168-7. [7] R. E. Jamison, A. P. Sprague, Double-threshold permutation graphs, Journal of Algebraic
Combinatorics (2021). doi:10.1007/s10801-021-01029-7. [8] G. Chen, Y. Hao, Multithreshold multipartite graphs, J. Graph Theory (2022) 1–6. doi:10.
1002/jgt.22805. [9] M. Xiao, H. Nagamochi, Characterizing Star-PCGs, Algorithmica 82 (2020) 3066–3090.
doi:10.1007/s00453-020-00712-8. [10] Y. Kobayashi, Y. Okamoto, Y. Otachi, Y. Uno, Linear-time recognition of double-threshold graphs, Algorithmica 84 (2022) 1163–1181. doi:10.1007/s00453-021-00921-9. [11] T. Calamoneri, D. Frascaria, B. Sinaimeri, All graphs with at most seven vertices are pairwise compatibility graphs, The Computer Journal 56 (2012) 882–886. URL: https: //doi.org/10.1093/comjnl/bxs087. doi:10.1093/comjnl/bxs087. [12] S. Durocher, D. Mondal, M. S. Rahman, On graphs that are not PCGs, Theoretical Computer
Science 571 (2015) 78–87. doi:10.1016/j.tcs.2015.01.011. [13] T. Calamoneri, A. Monti, F. Petroni, All graphs with at most 8 nodes are 2-interval-pcgs, 2022. URL: https://arxiv.org/abs/2202.13844. doi:10.48550/ARXIV.2202.13844. [14] OEIS Foundation Inc., Number of graphs on n unlabeled nodes. entry A000088, the On-Line
Encyclopedia of Integer Sequences, n.b. https://oeis.org/A000088. [15] H. N. de Ridder, et al., Information System on Graph Classes and their Inclusions (ISGCI), n.b. https://www.graphclasses.org/smallgraphs.html#nodes5.