2
$\begingroup$

Let's say I have a complete graph like this

W = {1, 2};
n = 5;
p2 = 0.5;
p1 = 1 - p2;
arr = {};
AppendTo[arr, RandomChoice[{p1, p2} -> {1, 2}, n]];
el1 = VertexList[CompleteGraph[n]];
g = CompleteGraph[n, 
  VertexLabels -> Table[el1[[i]] -> arr[[1]][[i]], {i, Length[el1]}], 
  VertexSize -> .10]
SeedRandom[1];
chain = {1,2,2};

There are 6 possible chains {1,2,2} for this particular graph enter image description here

I need to write a function that receives a complete graph g and a chain chain(1 < Length[chain] < n) and returns a number of such chains in g.

$\endgroup$
4
  • 1
    $\begingroup$ Look up "graph coloring"... a very well-developed field which uses colors instead of the labels 1 and 2. $\endgroup$ Commented May 30, 2023 at 22:27
  • 2
    $\begingroup$ Can you clarify, ideally through a concrete example, what you mean by "the number of required chains", or even what you mean by "chain" in this context? $\endgroup$
    – Szabolcs
    Commented May 31, 2023 at 9:59
  • 1
    $\begingroup$ is it always the case that Length[chain] <= VertexCount[g]? $\endgroup$
    – kglr
    Commented May 31, 2023 at 14:48
  • 1
    $\begingroup$ Yes, it is like that 1 < Length[chain] < n $\endgroup$
    – mclord
    Commented May 31, 2023 at 14:56

1 Answer 1

3
$\begingroup$
$Version
"13.1.0 for Linux x86 (64-bit) (June 16, 2022)"
ClearAll[chainCount]

chainCount[g_, p_] /; SubsetQ[Values@AnnotationValue[g, VertexLabels], p] := 
 Module[{cp = Counts @ p, 
   cg = Counts @ Values @ AnnotationValue[g, VertexLabels]}, 
  Apply[Times] @
   MapApply[FactorialPower] @
    Select[Length @ # == 2 &] @ Merge[Identity] @ {cg, cp}]

chainCount[g_, p_] = 0;

Examples:

n = 5;
p = 0.5;
SeedRandom[1];
arr = RandomChoice[{1 - p, p} -> {1, 2}, n];

g = CompleteGraph[n, VertexLabels -> {v_ :> arr[[v]]}, VertexSize -> .10]


chainCount[g, {1, 2, 2}]
6
chainCount[g, {1, 1, 2}]
12
chainCount[g, {2, 2, 2}]
0
chainCount[g, {1, 1, 1}]
6
chainCount[g, {1, 2, 1, 1}]
12
$\endgroup$
2
  • $\begingroup$ Maybe I am missing something but, for example, chainCount[g, {1, 2, 2}] returns <|2 -> {2, 2}, 1 -> {3, 1}|> $\endgroup$
    – mclord
    Commented May 31, 2023 at 16:05
  • 2
    $\begingroup$ @mclord, could be version/os difference (I am using v13.0 for linux x86). Try also starting with a fresh kernel. $\endgroup$
    – kglr
    Commented May 31, 2023 at 16:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.