# Tagged Questions

**6**

votes

**1**answer

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

**2**

votes

**1**answer

422 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

**2**answers

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

**0**answers

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

**11**

votes

**2**answers

206 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

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

**0**

votes

**1**answer

271 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

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

**11**

votes

**1**answer

845 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

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

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

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

**0**

votes

**0**answers

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

**-1**

votes

**0**answers

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

**5**

votes

**1**answer

403 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

385 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

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

**0**answers

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

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

277 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

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

**-4**

votes

**0**answers

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

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

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

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

247 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

562 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

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

**2**

votes

**0**answers

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

**3**

votes

**1**answer

322 views

### inequality with exponents

We are given a graph $G$, each vertex $v$ has an assigned value $\gamma_v\in [0,1]$, and it happens that for every $v$ we have $\gamma_v+\sum_{u\in \delta(v)} \gamma_u = 1$. Assume that $\sum_v ...

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

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

**9**

votes

**3**answers

463 views

### Disjoint Maximum Independent Sets in $\alpha$-critical graphs

Let $G$ be an undirected, simple graph, and let $\alpha(G)$ denote the independence number of $G$, i.e., the size of a maximum independent set (stable set) in $G$. A graph is $\alpha$-critical if for ...

**2**

votes

**1**answer

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

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

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

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

**3**

votes

**0**answers

185 views

### Bits required to encode difference between number of subgraphs with odd number of edges and number of subgraphs with even number of edges

Let $H = ( V, E )$ be a $k$-uniform connected hypergraph, with $n = |V|$ vertices and $m = |E|$ hyperedges. Let $O_w$ be the number of edge induced subgraphs of $H$ having $w$ vertices and an odd ...

**27**

votes

**0**answers

470 views

### What does this connection between Chebyshev, Ramanujan, Ihara and Riemann mean?

It all started with Chris' answer saying returning paths on cubic graphs without backtracking can be expressed by the following recursion relation:
$$p_{r+1}(a) = ap_r(a)-2p_{r-1}(a)$$
$a$ is an ...

**0**

votes

**1**answer

90 views

### Finding many disjoint sub-trees with many leaves

Let $T$ be a rooted binary tree with $L$ leaves, and let $\ell$ be a natural number smaller than $L$. The question is what is the maximal number of disjoint rooted sub-trees with at least $\ell$ ...

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