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

-3
votes
0answers
46 views

The line graph of a complete graph [on hold]

Show that there exist a $\left\{P_{5},C_{4}\right\}$- decomposition of the graph $L(K_{9})$.
1
vote
0answers
44 views

Difference in the Four Color Theorem [on hold]

How is proving that any planar graph with maximum degree of four has a four coloring, different from proving the four color theorem? If they are different, then how would one prove it?
1
vote
0answers
62 views

Counting growing tree trajectories

I am looking for help: Beginning with a single node ($\circ$), at each discrete time step I can add a node/link pair to any node currently in the tree. Nodes are unlabelled and the tree is ...
5
votes
0answers
98 views

Has anyone seen these binary trees (Catalan-type related to the Gegenbauer polynomials and Motzkin paths)?

The OEIS entry A121448 enumerates binary trees with $n$ edges and $k$ vertices with outdegree 1. Has anyone seen these trees? The o.g.f. for this entry, $G(x,t)$, is essentially a discriminant ...
5
votes
1answer
132 views

Example to $2^\kappa\nrightarrow (3)^2_\kappa$, plus closed walks of odd length?

Let $\kappa$ be an infinite cardinal. Consider the following example to $2^\kappa\nrightarrow (3)^2_\kappa$. $V$ is a set of vertices, each of which is an element of $2^\kappa$. Color the edge ...
12
votes
1answer
1k views

Is deciding if one planar graph is dual to another really NP-hard (Wikipedia claim)?

Wikipedia claims (permanent link) without reference: Testing whether one planar graph is dual to another is NP-complete. Another claim with reference: For any plane graph G, the medial graph ...
0
votes
0answers
26 views

Mapping a grayscale image into weighted undirected graph

I am looking for a method in order to convert an image into a network. I have found the study Z. Wu, X. Lu, Y. Deng, Image edge detection based on local dimension: A complex networks approach. Physica ...
2
votes
0answers
77 views

Systematic treatment of folding and valued graphs

I'm going to say beforehand that this question has something of a "am I missing something?" flavor. I'm in that odd position mathematicians often find themselves, where a topic has been addressed ...
10
votes
2answers
415 views

Blinking graphs

For any simple graph $G$, assign its nodes a weight/bit of $0$ or $1$. Call this a bit assignment for $G$. Now, generate a new bit assignment as follows: Each node $x$'s bit is replaced by $1$ if the ...
6
votes
3answers
218 views

Numerical invariants for a graph or its complement that are bounded by some constant

I'm looking for numerical graph invariants that are bounded by a constant either for a graph $G$ or its complement $\bar{G}$. (The complement graph $\bar{G}$ has the same set of vertices as $G$ but ...
2
votes
1answer
53 views

Properties of bipartite graphs

For a connected bipartite graph $G$ are the two following properties equivalent: 1)Every minimal cycle in $G$ has length 4, that is every cycle of length strictly greater than 4 can be divided in ...
22
votes
10answers
820 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
1answer
94 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
32 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
51 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
80 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
49 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
41 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 ...
2
votes
1answer
53 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
45 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
21 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
132 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
60 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
70 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
58 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
56 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
14 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
109 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
50 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
107 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
101 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
166 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
103 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
72 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
69 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
78 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
149 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 ...