Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with graph-theory
Search options not deleted
user 12481
Questions about the branch of combinatorics called graph theory (not to be used for questions concerning the graph of a function). This tag can be further specialized via using it in combination with more specialized tags such as extremal-graph-theory, spectral-graph-theory, algebraic-graph-theory, topological-graph-theory, random-graphs, graph-colorings and several others.
2
votes
NP-hardness of vertex cover for 3-chromatic graphs
Yes, it is NP-hard via reduction to Independent Set in cubic (3-regular) graphs.
Cubic graphs different from $K_4$ are 3-colorable in polynomial time via Brooks' theorem and IS remains NP-hard for the …
- 25.4k
-2
votes
2
answers
215
views
Must an isomorphism preserving graph transformation preserve the order of the automorphism g...
Let $F$ be some function graph to graph which preserve graph isomorphism.
Example of such $F$ are the line graph, the $k$-subdivision of $G$
and many others.
$F$ need not preserve the order, the degre …
- 25.4k
1
vote
0
answers
115
views
Hard instances for this graph isomorphism algorithm based on powers of weighted adjacency ma...
In short, I found an algorithm for GI and the only hard instances
I found so far are non-isomorphic strongly regular graphs with
large automorphism groups.
Q1 What are hard instances for the alogrith …
- 25.4k
2
votes
0
answers
189
views
Permutation similarity of matrices with many distinct entries
This is related to graph isomorphism.
Here matrices are square $n \times n$ with non-negative integer entries.
Two matrices $A,B$ are permutation similar if there exist
permutation matrix $P$ such tha …
- 25.4k
0
votes
0
answers
86
views
Does it help for graph isomorphism to know power of the permutation matrix?
Here all matrices are square $n \times n$ with integer entries.
If you prefer, all entries are $0-1$.
Observation: the discrete logarithm for permutation matrices is
polynomial in $n$, since the large …
- 25.4k
1
vote
0
answers
144
views
Counting Hamiltonian cycles in graph and finding a coefficient of polynomial
Exact result is #P-Hard, so we are looking for bounds.
Let $G$ be simple graph or simple digraph and $A$ its
adjacency matrix. $A$ is $n \times n$ with entries only zeros or ones.
Let $K=\mathbb{Z}[x_ …
- 25.4k
3
votes
How many non-isomorphic, simple, connected graphs with 6 vertices are there?
The answer to the question is $112$.
This is available at OEIS:
Number of connected graphs with n nodes
You can enumerate small graphs with Nauty:
https://www.mankier.com/1/nauty-geng
Or try the follo …
- 25.4k
2
votes
1
answer
239
views
What is wrong with the experimental evidence against the semi strong perfect graph theorem?
We got experimental evidence against the semi strong perfect graph theorem
and would like to learn what is wrong with it.
From Recognizing the P4-structure of bipartite graph
The P4-structure of a gr …
- 25.4k
3
votes
2
answers
315
views
Relation graph isomorphism to discrete logarithm
$\DeclareMathOperator\ora{ora}$Let $A_0$ be the adjacency matrix of graph $G$ and $P_0$
permutation matrix of multiplicative order $\rho$.
Let $X$ be positive integer and $B_0=P_0^X A_0 P_0^{-X}$.
Q1 …
- 25.4k
5
votes
2
answers
521
views
Diffie Hellman cryptography based on graph isomorphism?
We got a cryptographic algorithm and computer implementation
based on graph isomorphism.
An isomorphism between two graphs is a bijection between their vertices that pre
serves the edges.
For a graph …
- 25.4k
1
vote
0
answers
185
views
Maximum independent set in dense graphs
Let $0 < A < 1$ and $G$ be connected d-regular graph
with degree $d=[A n]$. The density of $G$ is about $A$.
Q1 Are there constraints on $A$ such that finding maximum
independent set of $G$ is polyno …
- 25.4k
2
votes
2
answers
325
views
Polynomial time algorithm for rigid graph isomorphism
We found, implemented and tested algorithm
for graph isomorphism and it appears to be polynomial
time if the graph is rigid.
Q1 Is the algorithm below correct and polynomial time for rigid graphs?
A …
- 25.4k
1
vote
0
answers
72
views
Reduction maximum independent set to MIS in a very dense graph
We got a reduction maximum independent set to MIS in a very dense graph,
or alternatively negative monotone 2-CNF to MAX-ONEs with a formula
with many clauses.
Let $G$ be graph of order $n$ and adjace …
- 25.4k
1
vote
0
answers
173
views
Reduction graph isomorphism to maximum independent set in very dense graph
We got a reduction graph isomorphism to MIS in a very dense graph,
or alternatively negative monotone 2-CNF to MAX-ONEs with a formula
with many clauses.
Let $G,H$ be graphs of order $n$ and adjacency …
- 25.4k
2
votes
0
answers
118
views
Complete graph invariant based on integer programming?
Roughly speaking, we are trying to find complete graph invariant
as the lexicographically first matrix from the permutations
of the adjacency matrix.
Let $G$ be graph, possibly directed graph, of orde …
- 25.4k