# Tagged Questions

**-3**

votes

**0**answers

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

**0**answers

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

**0**answers

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

**0**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**0**answers

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

**2**answers

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

**3**answers

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

**1**answer

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

**10**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**2**answers

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

**0**answers

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

**0**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**0**answers

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

**0**answers

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

**0**answers

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

**2**answers

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

**0**answers

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

**0**answers

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

**0**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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

**0**answers

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

**2**answers

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

**0**answers

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

**1**answer

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