Questions tagged [graph-theory]
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.
5,148
questions
2
votes
0
answers
117
views
When polynomial GI implies polynomial (edge) colored GI?
(edge) colored graph isomorphism is GI which
preserves the colors (of edges if it is edge colored).
There are several reductions using transformations/gadgets
of (edge) colored GI to GI. For edge ...
2
votes
0
answers
73
views
Looking for similar centrality measurement on graph
I'm working on a graph problem somehow related to centrality measurement. Given an undirected, unweighted tree $T$ and a vertex $v$, let $D_i(v)$ be the set of vertices in $T$ that are i hops from $v$,...
3
votes
0
answers
191
views
Properties of a smallest tournament with domination number $k$
For some tournament $T$, let $\gamma(T)$ denote the cardinality of a smallest dominating set of $T$.
Denote by $f(k)$ the minimum number of vertices of a tournament $T$ having $\gamma(T) = k$.
From ...
1
vote
1
answer
280
views
Two definitions of genus for circle graphs
In the (very nice) article of Goldstein and Turner untitled Applications of Topological Graph Theory to Group Theory, the following definitions can be found:
Definitions: A circle graph is a pair $(G,...
9
votes
2
answers
533
views
Cubic graphs whose 2-factors all have the same cycle type
Let $G$ be a bridgeless cubic graph. I am interested in such graphs where all 2-factors are isomorphic (as graphs), i.e. have the same partition as cycle type. We'll say that this partition is ...
9
votes
1
answer
1k
views
Smallest Connected Graph for Given Degree Sequence
For a given integer sequence $(d_1, d_2,...,d_n)$, a natural question is if such a sequence is graphical, i.e. is a degree sequence of some graph. According to Erdős–Gallai theorem, A sequence of non-...
2
votes
0
answers
1k
views
NP-hard proof of optimization version of exact cover [closed]
Exact cover is NPC.
http://en.wikipedia.org/wiki/Exact_cover#Equivalent_problems
Given a collection $\mathcal{S}$ of subsets of a set $X$, an exact cover is a >>subcollection $\mathcal{S}^*$ ...
1
vote
1
answer
80
views
Resource on characterizations or properties of traceable graphs
I am looking for some resources that provide information on traceable graphs(paths containing a hamiltonian path). I have found a lot of information on hamiltonian graphs, but none on traceable graphs....
0
votes
0
answers
93
views
asymptotic notation with graph colouring
This is my first ever post so I hope this is an appropriate question.
Basically I am looking at the paper here: http://homepages.math.uic.edu/~mubayi/papers/biclique.pdf
Namely theorem 5.
Now, feel ...
5
votes
1
answer
102
views
Is a connected graph uniquely determined by its weighted 2-step graph?
This is an extension of a previous question: https://math.stackexchange.com/questions/876336/is-a-graph-uniquely-determined-by-its-weighted-2-step-graph/876357#876357. In that question I asked about ...
27
votes
2
answers
1k
views
Is this graph polynomial known? Can it be efficiently computed?
I am a physicist, so apologies in advance for any confusing notation or terminology; I'll happily clarify. To provide a minimal amount of context, the following graph polynomial came up in my research ...
8
votes
1
answer
375
views
Set system with prescribed intersection sizes
Questions: What is the asymptotic maximal size of a $4$-uniform (every set has 4 elements) set system $\mathcal{A}$ of subsets of $[n]$ such that, no two sets have size of their intersection $2$?
In ...
1
vote
2
answers
282
views
edge graph reconstruction conjecture : set vs multi set
Why is the edge reconstruction conjecture stated with the deck defined as the multi set of graphs formed by deleting one edge? Can someone give an example of two graphs such that the edge deleted ...
7
votes
2
answers
447
views
What is the number of noncrossing acyclic digraphs?
A noncrossing graph on $n$ vertices is a graph drawn on $n$ points numbered from $1$ to $n$ in counter-clockwise order on a circle such that the edges lie entirely within the circle and do not cross ...
5
votes
1
answer
188
views
Graphs where each edge belongs to the same number of 1-factors
Let $G$ be a simple connected graph that has at least one 1-factor. We'll define:
$G$ has property A iff it is edge-transitive.
$G$ has property B iff each edge belongs to the same number of 1-factors....
2
votes
0
answers
458
views
Computing the chromatic polynomial of graph modulo $x-3$
The chromatic polynomial of graph $P(G,x)$ is univariate
polynomial which counts the number of colorings of $G$
with $x$ colors for natural $x$.
Graph is not $k$ colorable iff $P(G,k)=0$.
The ...
1
vote
1
answer
774
views
Vertex transitive and edge transitive and line graph
How can we find the proof of the following statement:
An undirected graph is edge transitive if and only if its line graph is vertex transitive.
25
votes
3
answers
1k
views
Removal of non-isomorphic edges results in the same graph
There exists a (simple unlabeled) graph on 6 nodes with a pair of non-isomorphic edges (i.e., there is no graph automorphism that sends one edge into the other) such that removal of either of them ...
10
votes
2
answers
573
views
Is every knot unavoidable in the embeddings of some graph?
Is it the case that, for any given knot $K$,
there exists some graph $G$ whose every embedding into $\mathbb{R}^3$
(or into $\mathbb{S}^3$)
contains a cycle that realizes $K$?
I know the famous ...
3
votes
1
answer
1k
views
How hard is a variant of graph automorphism problem?
I'm interested in a variant of graph automorphism problem (which is prime candidate for $NP$-Intermediate problem).
Restricted GA
Input: Given an undirected graph $G(E, V)$, and $\epsilon |V|/2$ pairs ...
3
votes
1
answer
298
views
Graph transformation related to graph isomorphism
Basically got graph transformation related to graph
isomorphism.
Define $G \to G'$. $V(G')=V(G) \cup E(G)=\{v_1\ldots v_n\} \cup \{e_1\ldots e_m\}$. Call $v_i$ vertices $v'$ and $e_i$ vertices $e'$.
...
13
votes
1
answer
4k
views
Surprising connection between linear algebra and graph theory
What is the intuition for linear algebra being such an effective tool to resolve questions regarding graphs?
For example, one can determine if a given graph is connected by computing its Laplacian ...
2
votes
1
answer
268
views
Minimum length path touching $n$ circles
Given $n$ non-overlapping circles of radius $1$ (i.e., the distance between the centers of any two circles is greater than $2$), how to find the minimum length path (the path can be of any form) that ...
3
votes
0
answers
57
views
Algorithm to construct metric space endomorphism with controlled square
Given a finite metric space $(M,d)$ with parameters $K \geq 1$ and $\epsilon > 0$, I'd like to algorithmically check for the existence of a non-identity map $\phi:M \to M$ which happens to be $K$-...
1
vote
1
answer
126
views
N random walkers that hit node v in a graph
Consider a finite, undirected graph G, with uniform edge weights. Assume that there are n number of random walkers that will start at different nodes (lets say n=3, hence the random walkers will start ...
2
votes
1
answer
100
views
About the diameter of a graph after removing orientation
This question was posted a few days ago on the Mathematics StackExchange, but so far it has not been answered. Let $G$ be a strongly connected directed graph of diameter $D$, and suppose that we ...
8
votes
0
answers
196
views
What is the probability of interpolating the Tutte polynomial of a planar graph from the values at the two hyperbolas?
The Tutte polynomial
is a bivariate polynomial with positive integer coefficient which is a graph
invariant and can be defined recursively.
Evaluating it is $\#P$-complete even when restricted to (...
2
votes
2
answers
2k
views
Strongly connected DAG from any connected undirected graph?
I have the following question. It seems likely to be true - can anyone provide a standard reference?
Given:
A connected, undirected graph.
Question 1:
Can we assume a single direction for each edge ...
6
votes
0
answers
301
views
Algorithms for computing the Resilience of Graphs
The definition of resilience with a graph $G$ w.r.t to a monotone property $\mathcal{P}$ is well known.
(Global resilience) Let $\mathcal{P}$ be an increasing monotone property. The global ...
3
votes
0
answers
119
views
Node covering in a random graph
Given $N$ nodes randomly placed in a $D\times D$ area, i.e., the position of each node is randomly chosen. Assume that both $N$ and $D$ are sufficiantly large.
An agent can move in the area at ...
0
votes
0
answers
240
views
Reduction from permanent to $(0,1)$-permanent and implication of $P \ne NP$
Valiant
shows reduction from counting the solutions of CNF formula $F$,$\#SAT(F)$
to computing permanent where $ Perm(A)= 4^{t(F)}\cdot \#SAT(F)$
for certain efficiently computable $t(F)$ and matrix $...
7
votes
2
answers
451
views
Find multiple non-adjacent paths in a graph
Consider a non-directed graph. I want to find as many non-adjacent paths as possible from a source $s$ to a destination $t$. Two paths $P_1$ and $P_2$ are said to be non-adjacent to each other if none ...
4
votes
1
answer
179
views
Product of geodesic distances
I'm working on trying to show this, but can't seem to get started. No guarantees that it is true, but other conditions on the adjacency matrix that make it true or a counter example are helpful. ...
0
votes
2
answers
165
views
different way of selecting a random graph
Consider having a 'base' graph $G=(V,E)$ and selecting each vertex with independent probability $p$ and having the induced subgraph of $G$ with all 'selected' points as your random graph. Has this ...
0
votes
4
answers
529
views
about the structure of components of tensor product if more than one bipartite graph is taken
I was reading about tensor product of graphs. We know that if we take tensor product of n graphs and want this product to be a connected graph then at most one graph should be bipartite. In the book ...
6
votes
1
answer
396
views
Graphs of lines on del Pezzo surfaces
Let $k$ be an algebraically closed field. To any del Pezzo surface $S$ over $k$ we may associate its graph of lines, which has one vertex for each line and an edge (with multiplicity if required) ...
2
votes
1
answer
1k
views
Clique problem for regular graphs
I am looking for NP complete results for cliques in regular graphs. For example is the general problem of determining if a regular graph on n vertices has an n/2 clique NP-complete? (obviously the ...
0
votes
0
answers
63
views
Paths on Cartesian products of graphs satisfying linear constraints
Assume integers $d > r > 0$ and a connected graph $G$ with $d$ vertices. Every point on the $r$-fold Cartesian product of $G$ with itself, $G^{\square r}$, is equivalent to a dimension-$d$ non-...
1
vote
0
answers
82
views
Empty node in cactus construction
Is there a necessary condition for not having empty node in the construction of the cactus of the minimum cuts of a graph?
In particular is there a necessary condition for not having empty k-junction ...
0
votes
0
answers
98
views
Correlation between attributes in a binary graph
Given an unrooted binary tree whose leaves are vertices of degree one that are labelled bijectively by a set $S$. We define a categorical attribute $A$ ($|A|<<|S|$) and each leaf is assigned a ...
1
vote
0
answers
215
views
Find a path that covers as many nodes as possible
I have the following interesting problem. Given a graph $G$, an agent starts to mark nodes in $G$ in the following way: it marks all nodes within distance $d$ from it. Now the question is to find the ...
18
votes
4
answers
5k
views
Expected number of connected components in a random graph
For a random graph G(n,p) what is the expected number of connected components? What is the probability distribution of this value?
I'm specially interested in what happens for small values of p, ...
-4
votes
1
answer
218
views
Bipartite graph [closed]
First of all, thank you for your time to reading my post.
I am a researcher but not a mathematician, i have some difficulties in solving a math problem, that why i am here to ask your help. I just ...
0
votes
1
answer
629
views
Kneser graphs eigenvalues
Basically, I want to prove that, in the Kneser graph (wikipedia has a good definition),$K_{n, m}$, if $n_{-}(A(G)) $ and $n_{+}(A(G))$ denote the number of negative and positive eigenvalues of A(G) ...
7
votes
2
answers
435
views
Conjecture: for perfect graphs the fractional chromatic index rounded up equals the chromatic index
Let $\chi'_f(G)$ be the fractional chromatic index.
Based on limited experiments (up to 8 vertices and few larger graphs),
I suspect:
Conjecture For perfect graphs $\lceil \chi'_f(G) \rceil = \chi'(...
1
vote
1
answer
147
views
Estimate for the travelling salesman problem for balls inside a grid
This question is probably easy but I only have "tedious case checking" proof strategy in sight, and I'm sure there should be a reference lying around...
The question concerns the TSP problem (with ...
7
votes
1
answer
912
views
Roots of matching polynomial of graph
At the end of this preprint, I make the following conjecture concerning the roots of the matching polynomial:
If a graph $G$ is connected and contains a cycle, then the spectral radius of $G$ ...
0
votes
1
answer
372
views
Finding node-disjoint routes with mutually exclusive nodes in graphs
I have the following problem. I would like to know if it reduces to some standard problem in Graph theory. Particularly, I would like to know whether it is NP-hard, if yes, how to prove its NP-...
1
vote
0
answers
80
views
Simulation of disassortative random graphs
Recently I have been trying to find a succinct algorithm for generation of disassortative networks. The best I have found is the algorithm by Newman described in his paper "Mixing patterns in networks"...
1
vote
0
answers
66
views
Polynomial problems in graph classes defined by forbidden induced cyclic subgraphs
Let $C$ be a graph class defined by a finite
number of forbidden induced subgraphs, all
of which are cyclic (contain at least one cycle).
Are there graph problems that can be solved in
polynomial ...