Add block and block-cactus recognition

[jplauri]

IGraphM has functionality for recognizing cactus graphs (IGCactusQ). These are precisely the graphs whose 2-connected components are cycles. On the other hand, there is no functionality for recognizing block graphs, that is, graphs whose 2-connected components are cliques. Should such a function be added as well?

For instance, this could be readily added as:

BlockQ[g_] := AllTrue[Subgraph[g, #] & /@ KVertexConnectedComponents[g, 2], CompleteGraphQ];

A natural variant is also given by block cactus graphs. These are the graphs for which each 2-connected component is a cycle or a clique. It should be straightforward to add such a function as well, if deemed interesting. For that, I guess there's no CycleGraphQ in Mathematica, but that can also be done as:

CycleGraphQ[g_] := (VertexCount[g] == 2 && EdgeCount[g] == 1) || Length[First[FindCycle[g]]] == EdgeCount[g];

Afterwards, BlockCactusQ would follow by replacing the condition CompleteGraphQ by the logical OR of the two conditions (clique or cycle).

To summarize, I think all of these would be useful additions besides IGCactusQ:

• IGCycleQ
• IGBlockQ
• IGBlockCactusQ

[jplauri]

As a side question, why does IGraphM have IGCompleteQ? Does it somehow differ from the one already in Mathematica, or which one should I use?

[szhorvat]

Originally, I did not notice CompleteGraphQ ...

IGCompleteQ differs in that it ignores multi-edges and self-loops.

In[25]:= glist = {Graph[{1 <-> 2}], Graph[{1 <-> 2, 1 <-> 1}], Graph[{1 <-> 2, 1 <-> 2}]};

In[26]:= IGCompleteQ /@ glist
Out[26]= {True, True, True}

In[27]:= CompleteGraphQ /@ glist
Out[27]= {True, False, False}

Implementing any kind of graph function is often a pain because we have to consider: directed/undirected, simple graph / multigraph / self-loops, weighted/non-weighted, and all combinations of these.

If we exclude non-simple graphs, then I guess CompleteGraphQ is better as it should be faster (not tested!)

[szhorvat]

@jplauri Is connectedness usually required for block graphs? The current IGCactusQ implementation does require it.

[jplauri]

Technically, either (block or cactus) can be disconnected. But maybe it's ok to require connectedness in both cases (but the docs should say this) - the user can just run the recognition on each component if necessary. Would that make sense?

[szhorvat]

Wikipedia and MathWorld include connectedness in their cactus definitions. Wikipedia also refers to cactus graphs as Husimi trees, where "tree" suggests connectedness. It mentions that "Husimi tree" is sometimes used to refer to block graphs instead, which suggests that at least some results about block graphs may assume connectedness (?)

I guess the question is: what behaviour is most useful and most convenient to users?

• If the function requires connectedness, one can always decompose a graph into components, and test each component separately.
• If the function does not require connectedness, one can additionally test for connectedness (which is more efficient than the previous option).

I guess the deciding factor is if most use cases would require testing for connectedness simultaneously anyway. I'd need some input here from someone who'd find this function of use.

[jplauri]

On a closer thought, I think it indeed makes sense to require connectnedness here. The reason is that these graphs are often defined via a block-cut tree which is a tree of biconnected components (these blocks are then all cliques/cycles depending on what we are defining).

Incidentally, I just had to do cactus recognition today so I came back to this post and perhaps hadn't seen your last post here earlier.