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

6
votes
1answer
117 views

What (fun) results in graph theory should undergraduates learn?

I have the task of creating a 3rd year undergraduate course in graph theory (in the UK). Essentially the students will have seen minimal discrete math/combinatorics before this course. Since graph ...
8
votes
2answers
77 views

How many uniquely colored degree two vertices in 3-coloring of subcubic graph?

Is there a graph with maximum degree three that has 3 degree two vertices that must get the same (resp. different) color in every 3-coloring of the graph? I'm interested in any similar results as ...
0
votes
0answers
23 views

How does subdividing an edge change the Tutte polynomial of graph at $x=0$?

Let $T_G(x,y)$ be the Tutte polynomial of simple graph $G$. Let $G'$ be $G$ with an edge subdivided (choose any edge). Limited experiments suggest: Conjecture 1: $T_G(0,y)=T_{G'}(0,y)$. Is ...
2
votes
1answer
45 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
73 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
51 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
48 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 ...
-1
votes
0answers
35 views

Graph theory - degree distribution

What is the relation (if there is one), between the probability to have an edge, to the degree distribution of a graph. For example: A graph that was created by Waxman model, the probability for an ...
0
votes
0answers
68 views

chromatic number of a graph and C++ programming [on hold]

Is there a graph library which already computes the chromatic number of a graph?...Maybe a home-made extension using Boost?... I just want to know if there exists exacts algorithms already ...
2
votes
1answer
46 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
44 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
77 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
20 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 ...
0
votes
0answers
23 views

random graph: edge creation probability [closed]

I apologize if this is something very trivial, but I couldn't find an answer to it anywhere: I have a directed graph with n = 280 nodes and ...
4
votes
1answer
123 views
+50

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 ...
-4
votes
0answers
22 views

Betweenness Centrality I want to find Betweenness Centrality of each node [closed]

enter image description here I want to find Betweenness Centrality of each node ...Can anyone please guide me
2
votes
1answer
57 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
150 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
69 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
90 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
57 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
12 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 ...
2
votes
0answers
53 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
131 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
13 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
19 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
21 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
108 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
23 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
79 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
49 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
106 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
53 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
0answers
99 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
163 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
102 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
71 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
65 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
77 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
148 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
54 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
162 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
105 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 ...
5
votes
0answers
85 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 ...
0
votes
0answers
11 views

Given a graph G = (V, E) prove e <= n(n-1)/2 for all n [migrated]

I'm trying to figure out to solve this problem: Given a graph G = (V, E) prove e <= n(n-1)/2 for all n, where e is the number of edges and n is the number of vertices. I'm thinking that I should ...
2
votes
1answer
92 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
69 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
82 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
108 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 ...