Hubbry Logo
CographCographMain
Open search
Cograph
Community hub
Cograph
logo
8 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Cograph
Cograph
Cograph
View on Wikipedia
from Wikipedia
The Turán graph T(13,4) is a cograph

In graph theory, a cograph, or complement-reducible graph, or P4-free graph, is a graph that can be generated from the single-vertex graph K1 by complementation and disjoint union. That is, the family of cographs is the smallest class of graphs that includes K1 and is closed under complementation and disjoint union.

Cographs have been discovered independently by several authors since the 1970s; early references include Jung (1978), Lerchs (1971), Seinsche (1974), and Sumner (1974). They have also been called D*-graphs,[1] hereditary Dacey graphs (after the related work of James C. Dacey Jr. on orthomodular lattices),[2] and 2-parity graphs.[3] They have a simple structural decomposition involving disjoint union and complement graph operations that can be represented concisely by a labeled tree and used algorithmically to efficiently solve many problems such as finding a maximum clique that are hard on more general graph classes.

Special types of cograph include complete graphs, complete bipartite graphs, cluster graphs, and threshold graphs. Cographs are, in turn, special cases of the distance-hereditary graphs, permutation graphs, comparability graphs, and perfect graphs.

Definition

[edit]

Recursive construction

[edit]

Any cograph may be constructed using the following rules:

  1. any single-vertex graph is a cograph;
  2. if is a cograph, so is its complement, ;
  3. if and are cographs, so is their disjoint union, .

The cographs may be defined as the graphs that can be constructed using these operations, starting from the single-vertex graphs.[4] Alternatively, instead of using the complement operation, one can use the join operation, which consists of forming the disjoint union and then adding an edge between every pair of a vertex from and a vertex from .

Other characterizations

[edit]

Several alternative characterizations of cographs can be given. Among them:

  • A cograph is a graph which does not contain the path P4 on 4 vertices (and hence of length 3) as an induced subgraph. That is, a graph is a cograph if and only if for any four vertices , if and are edges of the graph then at least one of or is also an edge.[4]
  • A cograph is a graph all of whose induced subgraphs have the property that any maximal clique intersects any maximal independent set in a single vertex.
  • A cograph is a graph in which every nontrivial induced subgraph has at least two vertices with the same neighbourhoods.
  • A cograph is a graph in which every nontrivial connected induced subgraph has a disconnected complement.
  • A cograph is a graph all of whose connected induced subgraphs have diameter at most 2.
  • A cograph is a graph in which every connected component is a distance-hereditary graph with diameter at most 2.
  • A cograph is a graph with clique-width at most 2.[5]
  • A cograph is a comparability graph of a series-parallel partial order.[1]
  • A cograph is a permutation graph of a separable permutation.[6]
  • A cograph is a graph all of whose minimal chordal completions are trivially perfect graphs.[7]
  • A cograph is a hereditarily well-colored graph, a graph such that every greedy coloring of every induced subgraph uses an optimal number of colors.[8]
  • A graph is a cograph if and only if every vertex order of the graph is a perfect order, since having no P4 means that no obstruction to a perfect order will exist in any vertex order.

Cotrees

[edit]
A cotree and the corresponding cograph. Each edge (u,v) in the cograph has a matching color to the least common ancestor of u and v in the cotree.

A cotree is a tree in which the internal nodes are labeled with the numbers 0 and 1. Every cotree T defines a cograph G having the leaves of T as vertices, and in which the subtree rooted at each node of T corresponds to the induced subgraph in G defined by the set of leaves descending from that node:

  • A subtree consisting of a single leaf node corresponds to an induced subgraph with a single vertex.
  • A subtree rooted at a node labeled 0 corresponds to the union of the subgraphs defined by the children of that node.
  • A subtree rooted at a node labeled 1 corresponds to the join of the subgraphs defined by the children of that node; that is, we form the union and add an edge between every two vertices corresponding to leaves in different subtrees. Alternatively, the join of a set of graphs can be viewed as formed by complementing each graph, forming the union of the complements, and then complementing the resulting union.

An equivalent way of describing the cograph formed from a cotree is that two vertices are connected by an edge if and only if the lowest common ancestor of the corresponding leaves is labeled by 1. Conversely, every cograph can be represented in this way by a cotree. If we require the labels on any root-leaf path of this tree to alternate between 0 and 1, this representation is unique.[4]

Computational properties

[edit]

Cographs may be recognized in linear time, and a cotree representation constructed, using modular decomposition,[9] partition refinement,[10] LexBFS ,[11] or split decomposition.[12] Once a cotree representation has been constructed, many familiar graph problems may be solved via simple bottom-up calculations on the cotrees.

For instance, to find the maximum clique in a cograph, compute in bottom-up order the maximum clique in each subgraph represented by a subtree of the cotree. For a node labeled 0, the maximum clique is the maximum among the cliques computed for that node's children. For a node labeled 1, the maximum clique is the union of the cliques computed for that node's children, and has size equal to the sum of the children's clique sizes. Thus, by alternately maximizing and summing values stored at each node of the cotree, we may compute the maximum clique size, and by alternately maximizing and taking unions, we may construct the maximum clique itself. Similar bottom-up tree computations allow the maximum independent set, vertex coloring number, maximum clique cover, and Hamiltonicity (that is the existence of a Hamiltonian cycle) to be computed in linear time from a cotree representation of a cograph.[4] Because cographs have bounded clique-width, Courcelle's theorem may be used to test any property in the monadic second-order logic of graphs (MSO1) on cographs in linear time.[13]

The problem of testing whether a given graph is k vertices away and/or t edges away from a cograph is fixed-parameter tractable.[14] Deciding if a graph can be k-edge-deleted to a cograph can be solved in O*(2.562k) time,[15] and k-edge-edited to a cograph in O*(4.612k).[16] If the largest induced cograph subgraph of a graph can be found by deleting k vertices from the graph, it can be found in O*(3.115k) time.[15]

Two cographs are isomorphic if and only if their cotrees (in the canonical form with no two adjacent vertices with the same label) are isomorphic. Because of this equivalence, one can determine in linear time whether two cographs are isomorphic, by constructing their cotrees and applying a linear time isomorphism test for labeled trees.[4]

If H is an induced subgraph of a cograph G, then H is itself a cograph; the cotree for H may be formed by removing some of the leaves from the cotree for G and then suppressing nodes that have only one child. It follows from Kruskal's tree theorem that the relation of being an induced subgraph is a well-quasi-ordering on the cographs.[17] Thus, if a subfamily of the cographs (such as the planar cographs) is closed under induced subgraph operations then it has a finite number of forbidden induced subgraphs. Computationally, this means that testing membership in such a subfamily may be performed in linear time, by using a bottom-up computation on the cotree of a given graph to test whether it contains any of these forbidden subgraphs. However, when the sizes of two cographs are both variable, testing whether one of them is an induced subgraph of the other is NP-complete.[18]

Cographs play a key role in algorithms for recognizing read-once functions.[19]

Some counting problems also become tractable when the input is restricted to be a cograph. For instance, there are polynomial-time algorithms to count the number of cliques or the number of maximum cliques in a cograph.[4]

Enumeration

[edit]

The number of connected cographs with n vertices, for n = 1, 2, 3, ..., is:

1, 1, 2, 5, 12, 33, 90, 261, 766, 2312, 7068, 21965, 68954, ... (sequence A000669 in the OEIS)

For n > 1 there are the same number of disconnected cographs, because for every cograph exactly one of it or its complement graph is connected.

[edit]

Subclasses

[edit]

Every complete graph Kn is a cograph, with a cotree consisting of a single 1-node and n leaves. Similarly, every complete bipartite graph Ka,b is a cograph. Its cotree is rooted at a 1-node which has two 0-node children, one with a leaf children and one with b leaf children. A Turán graph may be formed by the join of a family of equal-sized independent sets; thus, it also is a cograph, with a cotree rooted at a 1-node that has a child 0-node for each independent set.

Every threshold graph is also a cograph. A threshold graph may be formed by repeatedly adding one vertex, either connected to all previous vertices or to none of them; each such operation is one of the disjoint union or join operations by which a cotree may be formed. [20]

Superclasses

[edit]

The characterization of cographs by the property that every clique and maximal independent set have a nonempty intersection is a stronger version of the defining property of strongly perfect graphs, in which there every induced subgraph contains an independent set that intersects all maximal cliques. In a cograph, every maximal independent set intersects all maximal cliques. Thus, every cograph is strongly perfect.[21]

The fact that cographs are P4-free implies that they are perfectly orderable. In fact, every vertex order of a cograph is a perfect order which further implies that max clique finding and min colouring can be found in linear time with any greedy colouring and without the need for a cotree decomposition.

Every cograph is a distance-hereditary graph, meaning that every induced path in a cograph is a shortest path. The cographs may be characterized among the distance-hereditary graphs as having diameter at most two in each connected component. Every cograph is also a comparability graph of a series-parallel partial order, obtained by replacing the disjoint union and join operations by which the cograph was constructed by disjoint union and ordinal sum operations on partial orders. Because strongly perfect graphs, perfectly orderable graphs, distance-hereditary graphs, and comparability graphs are all perfect graphs, cographs are also perfect.[20]

Notes

[edit]

References

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Cograph

View on Grokipedia
from Grokipedia
A cograph is an undirected simple graph in that contains no isomorphic to the on four vertices, denoted P₄. These graphs, also called complement-reducible graphs, can be recursively constructed starting from a single isolated vertex (K₁) through the operations of and the join operation (the complement of ). Equivalently, a graph is a cograph if every connected has a disconnected complement. The class of cographs was formally introduced in 1981 by Derek G. Corneil, Helmut Lerchs, and Lorna Stewart Burlingham as complement-reducible graphs, with the name "cograph" reflecting their closure under complementation. Cographs form a well-studied hereditary graph class, meaning that every of a cograph is also a cograph, and they are precisely the P₄-free graphs. A key structural representation for cographs is the cotree, a that encodes the graph's via unions and joins, enabling efficient algorithmic processing. Cographs are perfect graphs, as established by a 1974 result showing that P₄-free graphs satisfy the perfect graph property (where the chromatic number equals the clique number for every induced subgraph). They belong to several broader classes, including distance-hereditary graphs, comparability graphs, and trivially perfect graphs when also chordal. Recognition of cographs can be performed in linear time O(n + m) using modular decomposition or cotree construction algorithms. Applications of cographs span , such as in clustering genetic data, and , including efficient solutions for problems like path covers and domination on these graphs. They also appear in the study of power graphs of finite groups and secure domination problems, where the cograph structure simplifies analysis.

Definition

Forbidden induced subgraph

A cograph is defined as an undirected graph that contains no induced subgraph isomorphic to the path graph P4P_4 on four vertices. An induced subgraph on a set of vertices SS consists of all vertices in SS together with every edge from the original graph that connects two vertices in SS; this contrasts with a general subgraph, which allows deletion of some edges between vertices in SS. Thus, an induced P4P_4 comprises four vertices a,b,c,da,b,c,d with edges only between aa-bb, bb-cc, and cc-dd, forming a path without any additional edges such as aa-cc or bb-dd. The prohibition of this structure ensures that the graph avoids certain irreducible connected components that cannot be decomposed via complements or disjoint unions, leading to a hereditary class closed under these operations. The class of such graphs was first characterized by Seinsche in as those where every on at least two vertices is either disconnected or has a disconnected complement, and he proved this class consists of perfect graphs. Independently, Sumner () provided a similar characterization. The term "cograph," short for complement-reducible graph, was later introduced by Corneil, Lerchs, and Stewart Burlingham in , who established its equivalence to the recursive construction via disjoint unions and joins (complements of disjoint unions) starting from isolated vertices, and confirmed the P_4-freeness. Examples of cographs include the KnK_n for any nn, where dense edges prevent any induced path of length three; the empty graph Kn‾\overline{K_n} (edgeless on nn vertices), which lacks sufficient edges for P4P_4; and the of any two cographs, as induced subgraphs remain confined to components. The cycle C4C_4 is also a cograph, since its single set of four vertices induces a cycle, which includes an extra edge compared to P4P_4, not a P4P_4. In contrast, the cycle C5C_5 contains an induced P4P_4 on any four consecutive vertices and is not a cograph; similarly, all cycles CnC_n for n≥5n \geq 5 are excluded. A graph is a cograph if and only if its every is P4P_4-free. This characterization aligns with the cotree representation, where the graph is encoded by a with leaves as vertices and internal nodes indicating unions or joins.

Recursive construction

Cographs admit a recursive starting from the base case of a single isolated vertex, which is trivially a cograph. The two fundamental operations are the and the join. The of two cographs GG and HH, denoted G+HG + H, has vertex set V(G)∪V(H)V(G) \cup V(H) (with V(G)V(G) and V(H)V(H) disjoint) and edge set E(G)∪E(H)E(G) \cup E(H), preserving the internal structure of each without adding cross-edges. The join of GG and HH, denoted G×HG \times H, has the same vertex set but edge set E(G)∪E(H)∪{uv∣u∈V(G),v∈V(H)}E(G) \cup E(H) \cup \{uv \mid u \in V(G), v \in V(H)\}, adding all possible edges between the two components. A central theorem states that a graph is a cograph if and only if it can be obtained from isolated vertices by a finite sequence of disjoint unions and joins. This generative process ensures that the resulting graph remains P4-free, as the operations do not introduce induced P4 subgraphs: in the disjoint union, any induced subgraph lies entirely within one operand; in the join, the complete bipartite connections between components force any potential four-vertex path spanning both to include additional edges, preventing it from being induced. Conversely, every P4-free graph admits such a decomposition into these operations, establishing the equivalence between the recursive definition and the forbidden subgraph characterization. For example, the Km,nK_{m,n} arises as the join of two empty graphs on mm and nn vertices, respectively; each empty graph is itself the of mm (or nn) isolated vertices. This illustrates how the operations build structured graphs like balanced complete bipartite ones without inducing P4s, highlighting the generative power of the construction for modular graph families.

Characterizations

Cotree representation

A cotree provides a canonical tree representation for cographs, encoding their recursive construction through disjoint unions and joins. It is defined as a tree where the leaves correspond to the vertices of the cograph, and each internal node is labeled either 0 or 1. A label of 0 represents a disjoint union operation, meaning no edges exist between the subgraphs induced by the subtrees of its children, while a label of 1 represents a join operation, meaning every possible edge exists between those subgraphs. Two vertices in the cograph are adjacent if and only if the label of their lowest common ancestor in the cotree is 1. For a given cograph, the cotree is unique up to , providing a normalized encoding that distinguishes it from other representations like modular decomposition trees, though the two are closely related for cographs. In the standard normalized form, the root of a connected cograph is labeled 1, and the ordering of sibling subtrees follows a consistent convention, such as based on vertex labels. This uniqueness stems from the complement-reducible nature of cographs, ensuring a single hierarchical structure captures the graph's construction sequence. Cotrees can be constructed either top-down, starting from the full graph and recursively partitioning into modules based on union or join structures, or bottom-up, beginning with individual vertices and merging them according to adjacency patterns until the full graph is rebuilt. These approaches leverage the P4-free property of cographs to identify reducible components efficiently, though detailed algorithmic steps are beyond the scope of this representation. For example, the cotree of the KnK_n consists of a labeled 1 with a tree of internal nodes all labeled 1 leading to the nn leaves, reflecting the full join across all vertices. In contrast, the cotree for the edgeless graph on nn vertices (a disconnected cograph) has a labeled 0 with all internal nodes labeled 0, representing the of isolated vertices. The height of a cotree measures the depth of the recursive and relates to the graph's , as connected cographs have at most 2 due to their P4-free structure, limiting the number of label alternations needed along paths between leaves. Additionally, cotrees facilitate efficient queries, such as determining connected components by identifying subtrees under 0-labeled nodes at the level or computing adjacency in logarithmic time via operations.

Complement reducibility

A complement-reducible graph is defined as a graph that can be reduced to a collection of isolated vertices by repeatedly taking the complement of each of its connected components until no edges remain. This process leverages the structure of the graph and its complement to simplify it step by step, ensuring that at each , the connected components become disconnected in the complement, allowing further . The class of complement-reducible graphs is precisely the class of cographs, as established by the equivalence theorem showing that a graph admits this reduction if and only if it is P₄-free. This characterization highlights the iterative nature of complementation in revealing the modular structure inherent to cographs. The reduction process can also be understood through the identification of twin vertices: true twins (adjacent vertices with identical open neighborhoods) or false twins (non-adjacent vertices with identical open neighborhoods), which can be collapsed into a single vertex without altering the graph's essential properties. Taking the complement interchanges true and false twins, enabling the process to continue until a single vertex remains. As an example, consider the P₃ on vertices a, b, c with edges a-b and b-c. This graph is connected, so take its complement, which consists of the edge a-c and an isolated vertex b. The connected component (the edge a-c) is then complemented to two isolated vertices, resulting in three isolated vertices overall. This demonstrates the reduction for a simple cograph. For threshold graphs, a subclass of cographs constructed by successively adding isolated or dominating vertices, the reverse process involves removing such vertices (or their counterparts in the complement) until reduction to an isolated vertex is achieved. This complement reducibility explains why cographs are perfect graphs: the absence of induced P₄ ensures no induced odd holes (cycles of length at least 5) or odd antiholes (complements of such cycles), as any such forbidden structure would contain a P₄. Since the complement of a cograph is also a cograph, both the graph and its complement avoid these imperfections. The cotree representation visualizes these reduction steps in reverse, with union and join operations corresponding to the path.

Properties

Structural properties

Cographs exhibit a high degree of modularity, characterized by the presence of non-trivial modules in every induced subgraph. Specifically, a module in a graph is a subset of vertices that have identical neighborhoods outside the subset, and a non-trivial module contains at least two vertices. Cographs are precisely the graphs in which every non-trivial induced subgraph contains at least one non-trivial module, manifested as at least two vertices sharing the exact same open neighborhood. As a subclass of distance-hereditary graphs, cographs preserve distances in and possess bounded within their components. In particular, every connected of a cograph has a of at most 2, ensuring that any two vertices are either adjacent or share a common neighbor. This property follows directly from the absence of , as a path of 3 would violate the diameter bound. Every cograph can be expressed as the intersection of two threshold graphs, where the edge set of the cograph is the common edges of the two threshold graphs on the same vertex set. This representation highlights the structural simplicity of cographs relative to the broader class of graphs. Connected cographs admit a partition of their vertex set into two modules via their join . In this bipartition, the two modules induce disjoint cographs, and every possible edge exists between vertices in different modules, forming a complete join. This structural feature is recursively defined in the cotree representation, where the corresponds to a join operation. The class of cographs is closed under taking complements: if G is a cograph, then its complement \overline{G} is also a cograph. This self-complementarity arises from the recursive construction, as the complement of a disjoint union is a join, and vice versa, preserving the P₄-free property.

Graph invariants

Cographs are perfect graphs: for every induced subgraph HH of a cograph GG, the chromatic number χ(H)\chi(H) equals the clique number ω(H)\omega(H). This equality simplifies the study of coloring properties in cographs, as the minimum number of colors needed to color any induced subgraph matches the size of its largest . The chromatic number of a cograph admits a recursive formula based on its construction via s and joins. For the G∪HG \cup H of two cographs GG and HH, χ(G∪H)=max⁡{χ(G),χ(H)}\chi(G \cup H) = \max\{\chi(G), \chi(H)\}. For the join G×HG \times H, which adds all possible edges between vertices of GG and HH, χ(G×H)=χ(G)+χ(H)\chi(G \times H) = \chi(G) + \chi(H). These formulas extend naturally to cotree representations, where invariants propagate bottom-up: starting from leaves (single vertices with χ=1\chi = 1), union nodes take the maximum over children, and join nodes sum the values over children. For example, the KnK_n, constructed as the join of nn singletons, has χ(Kn)=n\chi(K_n) = n, matching ω(Kn)=n\omega(K_n) = n. The independence number α(G)\alpha(G), the size of the largest independent set in GG, follows analogous recursive rules. For the G∪HG \cup H, α(G∪H)=α(G)+α(H)\alpha(G \cup H) = \alpha(G) + \alpha(H), as independent sets can combine freely across components. For the join G×HG \times H, α(G×H)=max⁡{α(G),α(H)}\alpha(G \times H) = \max\{\alpha(G), \alpha(H)\}, since no independent set can include vertices from both sides. Using the cotree, these values compute efficiently by propagating: union nodes sum child values, and join nodes take the maximum. For instance, the empty graph on nn vertices (disjoint union of singletons) has α=n\alpha = n. Connected cographs exhibit particularly simple distance properties, with at most 2: any two non-adjacent vertices share a common neighbor. This bounded underscores the structural compactness of cographs, limiting the longest shortest path to two edges in connected components. The cotree representation facilitates efficient of such invariants by bottom-up evaluation along the decomposition .

Algorithms

Recognition and decomposition

Cographs can be recognized in linear time, placing the problem in the complexity class , in contrast to many general graph recognition problems that are NP-complete. Early recognition algorithms from the , such as the O(n^4) method by Cowan et al., relied on checking complement reducibility through exhaustive searches for reducible vertices. These were improved to O(n^3) by and Maurer in 1979 via more efficient module identification. The breakthrough to linear time came in 1985 with the algorithm by Corneil, , and Stewart, which incrementally builds a cotree representation while verifying the structure. Further simplifications appeared in the and , culminating in the 2008 LexBFS-based approach by Bretscher et al., which computes the modular in O(n + m) time and confirms cograph status through ordering verification. One standard method for recognition tests whether the graph is P_4-free, as cographs are precisely the graphs without an induced path on four vertices (P_4). This can be achieved by scanning for induced P_4s using lexicographic (LexBFS), which produces orderings that allow efficient detection of forbidden subgraphs. In the Bretscher et al. algorithm, two LexBFS sweeps generate vertex orderings σ and τ; the graph is a cograph , for every vertex v, its neighbors in the ordering σ form a consecutive segment in τ (and vice versa, with complement checks). If a violation occurs, an induced P_4 can be exhibited as a certificate of non-cograph status. This approach leverages the fact that LexBFS preserves modular structure, enabling the P_4-free test in linear time without explicit enumeration of all potential P_4s. The modular provides a way to recognize cographs and construct their , as the decomposition tree for a cograph corresponds exactly to the cotree with union (0) and join (1) operations. Bretscher et al.'s computes this decomposition in O(n + m) time by using the LexBFS orderings to partition vertices into modules—subsets with identical external neighborhoods—and recursively verifying the prime/series/parallel structure, rejecting non-cographs along the way. For cographs, modules align with disjoint unions or joins, ensuring the decomposition builds a valid cotree. Implementations of these recognition and decomposition procedures are available in software libraries, and can be used for visualizing cotree output. Cotree construction proceeds bottom-up by iteratively identifying and contracting modules corresponding to the recursive construction of cographs. A high-level pseudocode outline, based on the incremental approach of Corneil et al., is as follows:

function BuildCotree(G): if |V(G)| == 1: return leaf node for the single vertex else: Find a non-trivial module M in G // Using adjacency checks or ordering if induced subgraph G[M] is disconnected: Create union node (0) as parent Recurse on connected components of G[M] as children Attach the cotree for G - M as sibling subtree elif complement of G[M] is disconnected: Create join node (1) as parent Recurse on co-components of G[M] as children Attach the cotree for G - M as sibling subtree else: Reject: G is not a cograph Return the root of the constructed tree

function BuildCotree(G): if |V(G)| == 1: return leaf node for the single vertex else: Find a non-trivial module M in G // Using adjacency checks or ordering if induced subgraph G[M] is disconnected: Create union node (0) as parent Recurse on connected components of G[M] as children Attach the cotree for G - M as sibling subtree elif complement of G[M] is disconnected: Create join node (1) as parent Recurse on co-components of G[M] as children Attach the cotree for G - M as sibling subtree else: Reject: G is not a cograph Return the root of the constructed tree

This process repeats until the entire graph is decomposed, with each step taking amortized constant time per edge in the linear-time framework, yielding the full cotree in O(n + m). The recursive construction serves as the basis for verifying the decomposition at each level.

Isomorphism testing

Isomorphism testing for cographs can be performed in time, specifically in O(n log n) time where n is the number of vertices, by leveraging their cotree representations. This contrasts with the general , which is GI-complete and not known to be solvable in time. The efficiency for cographs stems from their structured into cotrees, which uniquely capture the graph's via disjoint unions and joins. The algorithm begins by constructing the cotree for each input graph in linear time O(n + m), where m is the number of edges, using a modular approach that identifies series-parallel structure without induced P4s. To test , the cotrees are normalized into forms by recursively assigning labels to subtrees—such as strings representing their structure and leaf orders—and sorting the children of each internal node based on these labels or simpler invariants like subtree sizes. The structures are then compared recursively: two cotrees are isomorphic if their roots have the same label (0 for union or 1 for join), the same number of children, and pairwise isomorphic sorted subtrees. A key theorem states that two cographs are isomorphic if and only if their cotrees are isomorphic as labeled trees. For disconnected cographs, the root is a 0-node whose children represent the connected components, which are sorted by their canonical forms before comparison, ensuring the algorithm handles multiplicity correctly. The O(n log n) time arises primarily from the sorting steps across all nodes, as the total size of subtrees sums to O(n) and each sort costs up to O(n log n) in the worst case. No significant post-2020 improvements to this linearithmic bound have been reported, as the approach remains optimal given the structural constraints.

Enumeration

Counting formulas

The number of labeled cographs on nn vertices, denoted LnL_n, satisfies the exponential generating function equation G(x)=eC(x)G(x) = e^{C(x)}, where G(x)=∑n≥0Lnxnn!G(x) = \sum_{n \geq 0} L_n \frac{x^n}{n!} is the exponential for all labeled cographs (with L0=1L_0 = 1) and C(x)=∑n≥1Cnxnn!C(x) = \sum_{n \geq 1} C_n \frac{x^n}{n!} is the exponential for connected labeled cographs (CnC_n the corresponding count). The function C(x)C(x) solves the eC(x)−2C(x)+x−1=0e^{C(x)} - 2C(x) + x - 1 = 0. This equation arises from the cotree representation of cographs, where connected cographs correspond to cotrees rooted at a join operation (label 1), and the factor of 2 accounts for symmetries in the recursive join construction to avoid overcounting identical graphs under label permutations. The sequence LnL_n is given by OEIS A006351 and begins 1, 2, , 52, 472, 5504 for n=1n = 1 to 6.
nnLnL_n (labeled cographs)
11
22
3
452
5472
65504
778416
81320064
925637824
10564275648
The number of unlabeled cographs on nn vertices, denoted gng_n, has ordinary generating function G(x)=∑n≥0gnxn=exp⁡(∑k=1∞ckxkk)G(x) = \sum_{n \geq 0} g_n x^n = \exp\left( \sum_{k=1}^\infty c_k \frac{x^k}{k} \right), where ckc_k is the number of connected unlabeled cographs on kk vertices (OEIS A000669). This reflects the fact that unlabeled cographs are unordered disjoint unions of connected unlabeled cographs, enumerated via the exponential formula for . The sequence gng_n is OEIS A000084, with values 1, 2, 4, 10, 24, 66, 180, 522, 1532, 4624 for n=1n = 1 to 10. Enumeration of gng_n follows from the cotree construction, allowing arbitrary at union and join nodes. Explicit uses the connected counts cnc_n, via gn=∑m=1n1m!∑λ⊢n,λ has m parts∏cλjg_n = \sum_{m=1}^n \frac{1}{m!} \sum_{\lambda \vdash n, \lambda \text{ has } m \text{ parts}} \prod c_{\lambda_j} over partitions, but practical evaluation leverages the . The connected unlabeled counts cnc_n satisfy a similar recursive buildup from joins of smaller cographs, with c1=1c_1 = 1 and for n>1n > 1, cnc_n summing over isomorphisms of joins of smaller cographs. These were first systematically computed in the using Pólya techniques adapted to the complement-reducible of cographs.

Asymptotic behavior

The number of labeled cographs on nn vertices, denoted LnL_n, satisfies Ln∼n!πn3(2log⁡2−1)⋅(2log⁡2−1)−nL_n \sim \frac{n!}{\sqrt{\pi n^3 (2 \log 2 - 1)}} \cdot (2 \log 2 - 1)^{-n}
Add your contribution
Related Hubs
User Avatar
No comments yet.