Enable JavaScript to interact with content and submit forms on Wolfram websites. Learn how

Wolfram Language & System Documentation Center

LuccioSamiComponents

LuccioSamiComponents

LuccioSamiComponents[g]

gives the Luccio–Sami components of the graph g.

LuccioSamiComponents[g,{v₁,v₂,…}]

gives the components that include at least one of the vertices v₁, v₂, … .

LuccioSamiComponents[{vw,…},…]

uses rules vw to specify the graph g.

Details

LuccioSamiComponents is also known as an LS set.
A Luccio–Sami component is a set of vertices where each proper subset has more ties to its complement within the set than to the outside.
LuccioSamiComponents returns a list of components {c₁,c₂,…}, where each component c_i is given as a list of vertices.
LuccioSamiComponents[g] is equivalent to LuccioSamiComponents[g,VertexList[g]].
LuccioSamiComponents works with undirected graphs, directed graphs, multigraphs, and mixed graphs.

Examples

open all close all

Basic Examples (1)

Give the Luccio–Sami components for a graph:

Wolfram Language code: LuccioSamiComponents[[image]]

Scope (6)

LuccioSamiComponents works with undirected graphs:

Wolfram Language code: LuccioSamiComponents[[image]]

Directed graphs:

Wolfram Language code: LuccioSamiComponents[[image]]

Multigraphs:

Wolfram Language code: LuccioSamiComponents[[image]]

Mixed graphs:

Wolfram Language code: LuccioSamiComponents[[image]]

Give the components that include at least one of the vertices:

Wolfram Language code: LuccioSamiComponents[[image], {1, 3}]

Use rules to specify the graph:

Wolfram Language code: LuccioSamiComponents[{1 -> 2, 1 -> 3, 2 -> 4, 3 -> 4, 3 -> 5, 4 -> 6, 5 -> 6}]

Applications (1)

Highlight all Luccio–Sami components in a graph:

Wolfram Language code: g = [image];

Wolfram Language code: Table[HighlightGraph[g, Subgraph[g, i], VertexSize -> 0.2], {i, LuccioSamiComponents[g]}]

Properties & Relations (2)

All Luccio–Sami components are lambda components:

Wolfram Language code: g = [image];

Wolfram Language code: LuccioSamiComponents[g]

Wolfram Language code: LambdaComponents[g]

Wolfram Language code: MemberQ[LuccioSamiComponents[g], Alternatives @@ LambdaComponents[g]]

The converse is not always true:

Wolfram Language code: MemberQ[LambdaComponents[g], {5, 6, 7, 8}]

Wolfram Language code: MemberQ[LuccioSamiComponents[g], {5, 6, 7, 8}]

Luccio–Sami components are partially ordered by inclusion:

Wolfram Language code: g = [image];

Wolfram Language code: λ = LuccioSamiComponents[g]

The corresponding directed acyclic graph:

Wolfram Language code:

AdjacencyGraph[λ, Table[Boole@(SubsetQ[λ[[j]], λ[[i]]] && λ[[i]] != λ[[j]]), {i, Length[λ]}, {j, Length[λ]}], VertexLabels -> "Name", ImagePadding -> 10]

Wolfram Language code: AcyclicGraphQ[%]

Top