4
votes
2answers
101 views

How to obtain all the distinct De Bruijn sequences?

In combinatorial mathematics, a $k$-ary De Bruijn sequence $B(k, n)$ of order $n$ is a cyclic sequence of a given alphabet $A$ with size $k$ for which every possible subsequence of length $n$ in $A$ ...
4
votes
1answer
104 views

The algorithm of ListGraphs[n,m]

I'm not sure if this is a Mathematica problem, math problem or a CS problem, so if this is off-topic please transfer it. In the package Combinatorica there is a ...
2
votes
1answer
100 views

How to compute the `Automorphisms` of graphs with multiple edges?

I try to compute the Automorphisms of graphs with multiple edges from its AdjacencyMatrix but failed. The following code shows ...
0
votes
1answer
52 views

How should my data be formatted for use with BetweennessCentrality?

A few weeks ago I asked this question. I am trying to upload my data which is an adjacency list for an undirected, unweighed graph and find the betweenness centrality. At the time I tried to use the ...
0
votes
1answer
106 views

How do I upload a graph as an adjacency list and find the betweenness centrality?

I have an undirected simple graph in a .txt file formatted as an adjacency list like this: 100 200 200 300 300 400 500 600 700 800 900 ... Every number is a node ...
6
votes
3answers
187 views

Enumerate the 1-factors (perfect matchings) of $K_n$

Introduction I would like to enumerate the 1-factors, or (near-)perfect matchings, of the complete graph Kn. The adjacency list representation for Kn is basically { (x, y) | 1 ≤ x < y ≤ n }. For ...
2
votes
2answers
80 views

Checking connectedness of a graph

I am trying to use the Combinatorica package in a Mathematica version 8 in the following code: ...
5
votes
1answer
195 views

Shortest polygonal path

I'd like to find the shortest distance between some points (every point must be visited), such as between these 3 points: ...
1
vote
0answers
128 views

Tools for finding minimal or almost-minimal graph vertex colorations in Mathematica v9?

I'm looking to compute minimum vertex colorations (s.t. no two vertices of the same color share an edge: http://en.wikipedia.org/wiki/Graph_coloring) for graphs in Mathematica v9 with potentially up ...
2
votes
0answers
55 views

How to use Automorphisms[] on a graph? [duplicate]

I am having difficulty mixing the new post-Combinatorica graph data structure, with functionality apparently only in Combinatorica. I have constructed a graph using ...
5
votes
1answer
489 views

All possible topological orderings of a graph

TopologicalSort[] returns one of many unique orderings. From wikipedia: if a topological sort does not form a Hamiltonian path, the DAG will have two or ...
6
votes
2answers
337 views

Sierpinski carpet with GraphData

Is this graph in the list among the so-called "standard" structures used in GraphData? However, I have not found, yet, anything like "Carpet" or "Sponge" in the ...
1
vote
0answers
175 views

Get path to end nodes in directed (partially cyclic) graph

I have a large directed graph containing small loops. I would like to extract all paths to all end nodes (no VertexOutComponent) with a given path length $n$. I ...
6
votes
0answers
110 views

Is there a function to generate a minimal clique cover?

This is a graph problem known as the "Clique Edge Cover" or "Intersection Number" problem, and the goal is to find, from a given graph like $E=\{\{a,b\},\{a,c\},\{b,c\},\{b,d\},\{c,d\}\}$ and ...
2
votes
1answer
100 views

PermuteSubgraph not working? (Combinatorica)

I am trying to write a code to perform the QAP partialling analysis (here's a paper to know more) but the part in which I "scramble" the graph with PermuteSubgraph does nothing, I am actually not ...
4
votes
3answers
610 views

How to find all graph isomorphisms in FindGraphIsomorphism

I found the second definition of the function FindGraphIsomorphism not working. Here's the definition Mathematica 8 gives: ...
4
votes
1answer
461 views

(Efficiently) Generating graphs with vertex degree 3 for all vertices

I'm working on a graph theory problem, and given $n$ vertices, I would like to be able to generate all non-isomorphic connected graphs (not necessarily simple) with $n$ vertices, each having degree 3. ...
3
votes
2answers
281 views

Combinatorica: Girth[] and FindCycle[] disagreement

Warning: run the following code in a fresh Mma session, as some symbols could be shadowed (depending on your Mma version) While trying to answer this question, I fell into the following: ...
12
votes
4answers
1k views

Finding elementary cycles of (directed) graphs

I need to enumerate all the simple cycles (i.e. elementary cycles where no vertex is repeated other than the starting) of a graph which has both directed and undirected edges, where we can treat the ...
14
votes
3answers
488 views

Determining all possible traversals of a tree

I have a list: B={423, {{53, {39, 65, 423}}, {66, {67, 81, 423}}, {424, {25, 40, 423}}}}; This list can be visualized as a tree using ...
4
votes
1answer
1k views

Is it possible to generate a Hasse Diagram for a defined relation?

I'm looking for a way to create a Hasse Diagram from a given partial order binary relation. The relation will be given explicitly, for example: ...
14
votes
1answer
384 views

When to use built-in Graph/GraphPlot vs. Combinatorica

What are the pros and cons of using built-in Graph/GraphPlot (and related) types vs. types in the Combinatorica package?
3
votes
1answer
364 views

Combinatorica Graph from Edge List

Can someone provide an example of a Combinatorica-based graph which uses ShowGraph and Graph and takes in an explicitly defined list of edges (not some auto-generated graph). I have not been able to ...
10
votes
2answers
188 views

NumberOfSpanningTrees command not working correctly

I am attempting to use the Combinatorica NumberOfSpanningTrees command for all n-cycle graphs from 3 to 30. I am trying to get a ...