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, ...

learn more… | top users | synonyms

2
votes
1answer
69 views

Induced matching of cycle

Definition: A graph $G$ is chordal if every induced cycle in $G$ has length 3, and is co-chordal if the complement graph $G^c$ is chordal.The co-chordal cover number, denoted $cochord (G)$, is the ...
1
vote
1answer
83 views

Vectors which average to zero over any graph neighborhood

Given an undirected connected graph on $n$ nodes, let $S$ be the subspace of vectors $x \in \mathbb{R}^n$ which satisfy $$\sum_{j \in N(i)} x_j = 0,$$ for all $i=1, \ldots, n$. Here $N(i)$ is the set ...
1
vote
2answers
58 views

Maximal Minimum Weight DAGs

In the case of undirected, connected graphs the name for the maximal cycle-free subgraph of minimal weight is called Minimum Spanning Tree, and the efficient algorithms for their calculation are well ...
1
vote
0answers
61 views

A property of minimal prime ideals in rings with finite chromatic number

Let $R$ be a commutative ring with identity. There are so many ways to associate a graph to $R$. Consider this: take the elements of $R$ (All elements including zero) as vertices an two distinct ...
3
votes
1answer
60 views

Complexity of counting MAXCUT in planar graphs — seemingly contradicting claims

Confusion is likely. Appears to me two papers give contradicting claims about the complexity of counting MAXCUT in planar graphs. Exact Max 2-SAT: Easier and Faster p. 6 However, counting the ...
1
vote
0answers
51 views

Directed graph Laplacian with exactly one negative eigenvalue

Let $G$ be a digraph with adjacency matrix $A =(A_{ij})$ where $A_{ij}=1$ if and only if there is a directed edge $i \to j$ and $A_{ij}=0$ otherwise. Let $D= (D_{ij})$ be the degree matrix with ...
5
votes
1answer
88 views

Characterization of non-isomorphic graphs but isomorphic total graphs?

Given a graph $G$, the total graph of $G$, denoted $T(G)$, is the graph with vertex set $V(G) \cup E(G)$, where $a$ and $b$ are adjacent in $T(G)$ if and only if they are adjacent or incident in $G$. ...
0
votes
0answers
31 views

Linear Program for Single Source Shortest Paths Tree

This question originates in quick, however wrong, idea to calculate a shortest paths tree in the presence of negative cycles. The essential motivation was that a linear program would determine binary ...
4
votes
1answer
143 views

Probability bound for perfect matching

Let $p<1$ be a constant. Consider two sets $A,B$, each with $n$ vertices. For each pair $(a,b)\in A\times B$, the edge between $a$ and $b$ appears with probability $p$, independently of the ...
2
votes
1answer
78 views

Spectrum of Laplacian matrix of an infinite tree graph

I'm having difficulty understanding a fact stated in a research paper I'm reading. Namely, let $T$ be a tree with all nodes of degree $4$ (ie, the root has $4$ daughter nodes and all other nodes have ...
2
votes
1answer
163 views

Extracting a full rank matrix from a 0-1 matrix

If $A$ is a $n\!\times\!n$ $0$-$1$ matrix of rank $k<n$. If ever possible, what would be an efficient way of extracting a full rank $k\!\times\!k$ sub-matrix of $A$ by removing columns and rows of ...
3
votes
1answer
76 views

Generalizations of the Triangle Removal Lemma to smaller exponents

The Triangle Removal Lemma states: For all $\epsilon > 0$, there is a $\delta > 0$ such that any graph on $n$ vertices with at most $\delta n^3$ triangles may be made triangle-free by ...
1
vote
0answers
98 views

The lattice of graphs under vertex abstractions

I am curious to know if the following structure has been studied, or if anything similar is in the literature. For $n \in \mathbb{N}$, let $G = ([n],E)$ be a digraph. A partition of a subset $V$ of ...
2
votes
0answers
105 views

Detecting Negative Cycles in Undirected Graphs

I recently faced the problem of quickly detecting negative cycles in undirected, weighted graphs. Resorting to the Bellman-Ford Algorithm, as commonly suggested, turned out to be very inefficient and ...
0
votes
0answers
16 views

Does this transformation graph to multigraph keeps some (multi)graph invariants related?

Consider the following transformation graph $G$ to multigraph $G'$. $V(G')=V(G)$. For the edges of $G'$ add a clique of $V(G')$. For each edge $e \in E(G)$ add parallel edge $e'$. So $G'$ is clique ...
3
votes
0answers
73 views

Graph adjacency grouping with geometric criteria

I start with a list of adjacent tetrahedra, where there are tight seals to one another along faces for two tetrahedra that are adjacent. The vertices belonging to these faces for both tetrahedra are ...
-3
votes
2answers
144 views

Does every 3-regular bridgeless graph have a perfect matching? [closed]

Let $G$ be a simple $3$-regular (every vertex has degree $3$) $2$-edge connected graph. Does $G$ contain a perfect matching?
0
votes
0answers
17 views

Complexity of computing the multivariate Tutte polynomial of clique where each edge have distinct label

The multivariate Tutte polynomial $Z_G(q,v)$ is generalization of the Tutte polynomial and each edge is labelled by variable $v_e$. $Z_G(q,v)$ is linear in $v_i$. Let $G$ be a clique where each edge ...
1
vote
0answers
20 views

Complexity of computing the Tutte polynomial of multigraph when the Tutte polynomial of the underlying simple graph is known

Let $G$ be multigraph with $l$ loops and $m$ multiple edges and $G'$ be the underlying simple graph (loops and multiple edges removed). Assume the Tutte polynomial of $G'$ is given. Q1 What is ...
0
votes
0answers
32 views

Non-adjacent Pair of Edges with Minimal Weight Sum

Given an weighted, undirected Graph $G(V,E)$ without loops or parallel edges, what is the complexity of determining a pair of non-adjacent edges, whose sum of weights is w.l.o.g. minimal? ...
2
votes
1answer
117 views

Name for the set of vertices with the same neighborhood as another vertex

Suppose $\Gamma$ is a simple graph and $N_{\Gamma}(g)=\{x\in V(\Gamma)|x\sim g\}$ is the neighborhood of $g\in V(\Gamma)$. Then consider $$\mathbb{S}=\{y\in V(\Gamma)|N_{\Gamma}(y)=N_{\Gamma}(g)\}.$$ ...
1
vote
0answers
26 views

Some confusion regarding the definition of NPO reduction

I've seen the following definition in a paper on approximation preserving reductions. Definition:Let $\pi_{1}$ and $\pi_{2}$ be two NPO maximization problems. Then we say that $\pi_{1} \leq_{R} ...
2
votes
1answer
86 views

Orthogonal embeddings and edge lengths

I'm interested in orthogonal embeddings of graphs into the 2-dimensional, i.e where vertices are placed at integer co-ordinates and edges are routed along the grid lines and are not allowed to ...
0
votes
1answer
58 views

Reference Request: Graph Edge Density

I was curious if there was a reference which answers the question, What is the maximum number of edges in a graph $G$ with $n$ vertices which does not contain a $5$-cycle? $k$-cycle? The analogous ...
2
votes
0answers
111 views

Formulating shortest path as submodular minimization

I'm curious about the general question of whether any combinatorial optimization problem with polynomial time solution can necessarily be reformulated as minimizing a submodular function. The answer ...
2
votes
1answer
68 views

Minimum Edge Density given a particular condition

Consider a graph with $n$ vertices such that if one takes any 4 vertices there are at most 4 edges among these 4 vertices (Notice that there are 6 "possible" edges among these 4 vertices). What is the ...
2
votes
1answer
200 views

Variants of Szemeredi's regularity lemma

I've noticed that the name 'Szemeredi's regularity lemma' is used for several closely related yet different statements about graphs. Specifically, I'm interested in the distinction between two of ...
2
votes
1answer
185 views

Existence of Spanning Tree implies Well Ordering Principle

Every connected graph has a spanning tree. Every non-empty set can be well ordered. Basically I am trying to show that statement 1 implies statement 2. What I tried is as following: Let $X \ne ...
4
votes
1answer
128 views

Edge Reconstruction Conjecture

I have seen this question asked at least once before, but not with any real answers. I was reading about the various reconstruction conjectures and equivalents, and I saw that the reconstruction ...
3
votes
0answers
79 views

Is there a Havel-Hakimi for geometric graphs?

Suppose that we are given $n$ points in the plane, with a degree prescribed for each, and the question is whether we can place a geometric graph on them. Is there an efficient algorithm for this? ...
0
votes
1answer
75 views

Extremal problem: #paths of length l as function of number of edges

Suppose that $G$ is a simple, undirected graph with $n$ vertices and $m$ edges. Conjecture: The total number of vertex paths of length $l$ is at most $$ n (2 m/n)^{l-1} $$ The heuristic basis for ...
0
votes
0answers
83 views

Primitivity of $AA^\top$

Let $A\in\mathbb{R}^{n\times n}$ be a non-negative and irreducible matrix. Consider $B:=AA^\top$. It can be proved (I can post a proof if needed) that the following condition is necessary and ...
3
votes
2answers
156 views

Asymptotics of list size in Robertson-Seymour theorem

A planar graph cannot have $K_5$ and $K_{3,3}$ as minors. Robertson-Seymour theorem generalizes this by stating for every genus $g$ there is a finite list of forbidden minor graphs that are ...
1
vote
0answers
62 views

Building an orthogonal embedding for a 4-planar graph

I'm interested in the following paper http://www.computer.org/csdl/trans/tc/1981/02/06312176.pdf In particular i'm interested in the construction Valiant describes to prove that it is possible to ...
3
votes
1answer
175 views

A criterion for rooted trees to be isomorphic based on walks

Suppose you have two rooted trees $T_1$ and $T_2$ with roots $r_1$ and $r_2$, respectively. Furthermore, for every $k\ge 0$, the number of walks of $T_1$ starting at $r_1$ of length $k$ is equal to ...
1
vote
0answers
114 views

2-edge colorable graph approximation

A 2 edge-colorable graph is a graph in which we can color the edges with two colors, in a way such that no edges of the same color share a vertex. Given a graph G = (V,E) I want to find a 2 ...
6
votes
0answers
98 views

Is there a Ramsey theory for Kneser graphs?

Ramsey theory for graphs usually studies colorings of the edges of complete graphs. I'm interested whether there are any results about edge-colorings of Kneser graphs. More specifically, I'm most ...
2
votes
1answer
112 views

Bipartite dimension of an almost crown graph

A crown graph is a complete bipartite graph from which a perfect matching has been removed. The bipartite dimension of a graph is the minimum number of complete bipartite subgraphs needed to cover ...
6
votes
0answers
74 views

Contradicting claims about complexity of directed path graphs isomorphism

Thesis and a paper give conflicting claims about the complexity of graph isomorphism for directed path graphs. Since this means GI is polynomial likely I am missing something or there is something ...
-4
votes
2answers
95 views

Reconstructing a graph from the multiset of degrees

Suppose $G, H$ are finite, simple, undirected graphs and there is a bijection between the vertex sets $\varphi:V(G) \to V(H)$ such that for all $v\in V$ we have $$\text{deg}_G(v) = ...
0
votes
0answers
26 views

Name for a “Broken Cycles” Graph Problem

Is there a name for the task of reconstructing a set of cycles $\mathcal{C} = \{C_1,...,C_k\}$ in an undirected graph from the collection of $\mathcal{E}$ of edges constituting to $\mathcal{C}$, when ...
1
vote
1answer
113 views

diameter of Cayley graphs

For a group $G$ and an inverse closed subset $S$ of $G\setminus \{1\}$, the Cayley graph $Cay(G,S)$, is the graph whose vertices are the elements of $G$ and two vertices $x$ and $y$ are adjacent if ...
0
votes
0answers
34 views

Minimum weight odd cycle with certain edge pairs forbidden

Given a weighted graph $G=(V,E)$ and several disjoint sets $S_1, \dots, S_t \subset E$ of edges, is there a polynomial-time algorithm to find a minimum weight odd cycle which does not contain more ...
4
votes
1answer
115 views

Diameter vs Radius in Maximal Planar Graphs

Let $G$ be an undirected graph. The eccentricity of a vertex $v$ of $G$, is the maximum distance between $v$ and any other vertex of $G$:$\;\;$ $\mathit{ecc}(v) = \max_{u}\mathit{dist}(v,u)$. The ...
2
votes
1answer
144 views

Why is graph automorphism sometimes easier than canonical labeling (for current software)?

László Babai recently hinted that graph isomorphism is solved for all practical purposes: It seems, for all practical purposes, the Graph Isomorphism problem is solved; a suite of remarkably ...
28
votes
1answer
960 views

Should axiomatic set theory be translated into graph theory?

Recently I saw the abstract of a paper by Nash-Williams: ``Should axiomatic set theory be translated into graph theory?''. The abstract, taken from Mathscinet says the following: The author ...
1
vote
1answer
153 views

Conjecture of Kelly [closed]

In GTM 244,it writes: Two graphs G and H on the same vertex set V are called hypomorphic if, for all v ∈ V , their vertex-deleted subgraphs G − v and H − v are isomorphic.Does this imply that G and H ...
9
votes
0answers
104 views

Cycles of length $2^n - 2$ in the De Bruijn graph

It is well known that the number of (cyclic) De Bruijn sequences is $2^{2^{n-1}-n}$. This number may also be interpreted as the number of cycles of length $2^n$ in the De Bruijn graph of order $n$. ...
1
vote
0answers
31 views

Generate connected subgraphs as the satisfying assignments to a SAT instance

I want a SAT instance (in CNF) whose set of satisfying assignments are the connected subgraphs of a given input graph. A general solution would be helpful, but I really only need this when the input ...
-2
votes
1answer
66 views

Graph isomorphism for twin free graphs

Suppose you are given two graphs $G_1$ and $G_2$ and are promised that both are twin free. Is the problem of determining if they are isomorphic graph isomorphism hard? I am curious for the cases of ...