# Tagged Questions

**6**

votes

**1**answer

405 views

### How to find or constrain “particularly good” (two-sided) spectral expanders?

I'm new to graph theory, but a response to a question I asked a while ago introduced me to the concept of expander graphs.
A k-regular graph (henceforth "graph") on n nodes has eigenvalues k = λ1 ≥ ...

**-3**

votes

**0**answers

34 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})$.

**3**

votes

**1**answer

196 views

### Question about 3-regular graphs with a restriction (also fullerene and four color theorem)

(Crossposted from math.stackexchange.)
Studying all 3-regular graphs that have only faces with 5 edges or more (simplified), I empirically found (computer program) that many hypothetically possible ...

**1**

vote

**0**answers

32 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?

**4**

votes

**0**answers

58 views

+50

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

**10**

votes

**2**answers

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

**1**

vote

**0**answers

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

**22**

votes

**10**answers

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

**5**

votes

**0**answers

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

**0**

votes

**1**answer

332 views

### Number of labeled regular graphs on n vertices

What is known about the number of labeled regular graphs on n vertices? The sequence does not appear to be in the OEIS.

**3**

votes

**2**answers

237 views

### Partitioning a binary tree into vertex-disjoint subtrees

Say we have a labeled, binary unrooted tree $T$, i.e. each node has either 1 or 3 neighbors.
Denote by $L(T)$ the set of leaves (degree-one nodes) of $T$.
For some $L \subseteq L(T)$, denote by ...

**5**

votes

**1**answer

129 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

25 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

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

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

**15**

votes

**2**answers

1k views

### A generalization of the triangle counting problem for simple weighted graphs

One nice identity is that $$\operatorname{tr}(A^3)/6$$ counts the number of triangles of a graph with adjacency matrix $A$. It also implies that triangle counting in a graph can be performed in ...

**2**

votes

**1**answer

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

**2**

votes

**1**answer

431 views

### Polygamous stable marriage/ assignment problem

I'm not sure under which 'algorithm' it falls under, but here is the problem:
I need to match each person to 5 people from the opposite gender (each guy gets 5 girls, each girl gets 5 guys). Not all ...

**8**

votes

**1**answer

92 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

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

**11**

votes

**2**answers

208 views

### What are some useful invariants for distinguishing between random graph models?

Quite a few probabilistic algorithms for generating random graphs exist in the literature, such as:
The Erdős-Rényi model
The Stochastic Block model
The Watts-Strogatz model
The Barabasi-Albert ...

**2**

votes

**1**answer

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

**0**

votes

**1**answer

272 views

### Does this graph contain at least two Hamiltonian cycles?

Let $G$ be a simple graph which is a $2n$-cycle together with $n$ chords such that $G$ is $3$-regular. In other words, the set of $n$ chords is a perfect matching of $G$.
I conjecture that for every ...

**1**

vote

**3**answers

1k views

### Laplacian spectrum for product graphs

Let $G$ and $H$ be simple graphs.
I am interested in the Laplacian spectrum for various products of $G$ and $H$ namely the cartesian product, tensor product, lexicographical product and strong ...

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

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

**11**

votes

**1**answer

846 views

### Menger's theorem via matroids

Let $G=(V,E)$ be an oriented graph, $Y\subset V$ be some fixed set of its vertices. Call $A\subset V$ independent if there exist $|A|$ vertex-disjoint paths starting in $A$ and ending in $Y$. It is ...

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

**15**

votes

**11**answers

2k views

### Chromatic number of graphs of tangent closed balls

The Koebe–Andreev–Thurston theorem gives a characterization of planar graphs in terms of disjoint circles being tangent. For every planar graph $G$ there is a disk packing whose graph is $G$. What ...

**1**

vote

**0**answers

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

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

votes

**0**answers

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

**5**

votes

**1**answer

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

**2**

votes

**1**answer

387 views

### Complexity of bipartite graphs and their matchings.

My question concerns a hypothetical family of bipartite graphs, $G_i$.
Each graph $G_i$ has $2^i$ red nodes and $2^i$ blue nodes - so nodes get labelled
by their color and a binary string of ...

**1**

vote

**0**answers

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

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

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

**16**

votes

**2**answers

654 views

### Which graphs are elementarily equivalent to their own disjoint sums?

In Stefan Geschke's recent
question,
one of the solutions observed that the graph consisting of
a single infinite beaded chain, a $\mathbb{Z}$-chain where
each integer is connected to its nearest ...

**0**

votes

**1**answer

278 views

### finding missing edge in DAG which, when added, would create the longest cycle

Hey all,
Not sure if this is a math problem or an algorithm problem - but hoping it has a math style answer.
If I have a directed graph I can find all the closed loops - easy. (Actually not at all ...

**2**

votes

**1**answer

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

**16**

votes

**1**answer

858 views

### Determine or estimate the number of maximal triangle-free graphs on $n$ vertices

Among the collections of the open problems of Paul Erdős on the website of
Professor Fan Chung, there is one called "number of triangle-free graphs".
...

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

**7**

votes

**1**answer

1k views

### Counting non-isomorphic graphs with prescribed number of edges and vertices

I'd love your help with this question.
Let $n\geq3$ be a fixed integer. How many non-isomorphic graphs with $p$ vertices and $q$ edges are there where $p+q=n$?
Thank you very much.
Crossposted at ...

**7**

votes

**1**answer

537 views

### Bipartite Graphs arising from two k-partitions of a given Graph

Let $G$ be an $n$-chromatic connected graph. Let $(V_1, V_2, \cdots, V_n)$ and $(U_1, U_2, \cdots, U_n)$ be two partitions of $V(G)$ corresponding to proper n-colorings of $G$.
Consider the bipartite ...

**0**

votes

**1**answer

248 views

### Reverse optimization of a minimum cost flow network

Given an undirected graph $(V,E)$, with $W$ as the weight of each edge, and a convex cost function $F(X)$, such as $|X|^k$ ($k>1$).
The cost to send $x$ unit of flow through edge $e_i$ is defined ...

**13**

votes

**1**answer

563 views

### Bicycles and spanning trees of graphs

A spanning tree in a graph is a connected spanning subgraph with no cycles; it is well known that the number of spanning trees can be found by taking the determinant of a certain matrix related to the ...

**3**

votes

**2**answers

563 views

### Solving assignment problem using Hungarian method vs min cost max flow problem

The traditional solution for the assignment problem is the Hungarian method - it's complexity is O(V^4) or O(V^3) if using Edmonds method.
However, it can also be reduced to a min cost max flow ...