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.

Filter by
Sorted by
Tagged with
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 ...
joro's user avatar
  • 24.2k
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$,...
guawadd's user avatar
  • 21
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 ...
Manuel Lafond's user avatar
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,...
Seirios's user avatar
  • 2,361
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 ...
Wolfgang's user avatar
  • 13.2k
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-...
user avatar
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}^*$ ...
ulyssis2's user avatar
  • 121
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....
Gorka's user avatar
  • 1,825
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 ...
Shaun's user avatar
  • 1
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 ...
Paul Siegel's user avatar
  • 28.8k
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 ...
Mike Hermele's user avatar
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 ...
Daniel Soltész's user avatar
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 ...
Thinniyam Srinivasan Ramanatha's user avatar
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 ...
Marco Kuhlmann's user avatar
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....
Wolfgang's user avatar
  • 13.2k
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 ...
joro's user avatar
  • 24.2k
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.
Mojtaba Jazaeri's user avatar
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 ...
Max Alekseyev's user avatar
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 ...
Joseph O'Rourke's user avatar
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 ...
Mohammad Al-Turkistany's user avatar
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'$. ...
joro's user avatar
  • 24.2k
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 ...
rnegrinho's user avatar
  • 407
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 ...
lchen's user avatar
  • 459
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$-...
Vidit Nanda's user avatar
  • 15.4k
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 ...
user1894963's user avatar
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 ...
Hebert's user avatar
  • 105
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 (...
joro's user avatar
  • 24.2k
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 ...
user avatar
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 ...
Pavan Sangha's user avatar
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 ...
lchen's user avatar
  • 459
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 $...
joro's user avatar
  • 24.2k
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 ...
lchen's user avatar
  • 459
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. ...
Rob Richmond's user avatar
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 ...
Pavan Sangha's user avatar
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 ...
monalisa's user avatar
  • 101
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) ...
Daniel Loughran's user avatar
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 ...
richard taylor's user avatar
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-...
ematsen's user avatar
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 ...
user53189's user avatar
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 ...
Matt's user avatar
  • 11
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 ...
lchen's user avatar
  • 459
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, ...
Ramon's user avatar
  • 181
-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 ...
user3592519's user avatar
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) ...
user53083's user avatar
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'(...
joro's user avatar
  • 24.2k
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 ...
ARG's user avatar
  • 4,342
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$ ...
David Bevan's user avatar
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-...
lchen's user avatar
  • 459
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"...
Vladimir Stozhkov's user avatar
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 ...
joro's user avatar
  • 24.2k

1
69 70
71
72 73
103