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
0answers
139 views

Does the weak Hadwiger conjecture imply the Hadwiger conjecture?

For any cardinal $\kappa$, let $K_\kappa$ denote the complete graph on $\kappa$. We consider the following statements: (H) If $G$ is a graph and $\chi(G) = \kappa$ then $K_\kappa$ is a minor of $G$. ...
2
votes
1answer
108 views

irregular pairs in half graphs - Szemeredi regularity

Szemeredi's regularity lemma is a well-known result about partitioning large graphs into pieces such that most pairs of pieces are "regular". The precise statement takes a bit of detail so I'll just ...
12
votes
1answer
291 views

Coloring the edges of a torus graph

Question:Consider the $2k \times 2k$ grid graph on a torus. Is it true that for every $2$-coloring of the edges, there is an antipodal pair of vertices connected by a path that changes colors at most ...
9
votes
2answers
238 views

Vertex-primitive graphs with two vertices having almost the same neighbourhood

Hypothesis: Let $\Gamma$ be a vertex-primitive graph with two vertices $u$ and $v$ such that $$|N(u) \cap N(v)|=|N(v)|-1$$ Question: Is it true that $\Gamma$ must either be a complete graph or have ...
0
votes
1answer
38 views

Is it known whether Minimum Cost Multicut is APX-hard?

My questions is concerned with the following problem: Given an undirected graph $G = (V, E)$ and (edge costs) $c \in \mathbb{Z}^E$, $$\min \left\{ \sum_{e \in E} c_e x_e\ \middle|\ x \in \{0,1\}^E \ ...
0
votes
1answer
110 views

How to solve the opposite of max flow problem? [closed]

Each edge in graph has a minimum bound instead of a maximum capacity. The goal is to find the minimum flow such that every edge in graph has flow larger than it's lower bound. I tried to use Ford ...
7
votes
3answers
405 views

Is there a continuous analogue of Ramanujan graphs?

I think it might help to think of the following definition of a Ramanujan graph - a graph whose non-trivial eigenvalues are such that their magnitude is bounded above by the spectral radius of its ...
4
votes
0answers
121 views

minimal polynomial for a graph

I wonder if there is any result relating the degree $d$ of the minimal polynomial of a directed finite graph to any of its topological features - such as its diameter, or any other similar 'natural' ...
6
votes
2answers
235 views

Counting valid coordinates

We are given a matrix $D = (d(i,j))_{1 \leq i,j \leq n}$ such that $d(x,z) \leq d(x,y) + d(y,z)$ for each $1 \leq x,y,z \leq n$. It is also known that $d(x,y) \in \mathbb{N}$ (In this question $0 \in ...
2
votes
2answers
55 views

Deciding whether a given graph has an f-factor or not!

Given a graph $G$ with $n$ vertices and a function $f$ from $\{1,2,...,n\}$ to non-negative integers, Does there exist an efficient (for example polynomial time) algorithm, that decides whether $G$ ...
1
vote
1answer
152 views

Probability of each edge in K-clique [closed]

For $c \in R$ and $k \in N$, $k \geq 3$ let $p_{k,c} := n^{\frac{−2}{k+1}}log^c(n)$. I would like to prove that exists $c\in R$ such that every edge in the random graph $G(n,p_{k,c})$ lies in a copy ...
0
votes
1answer
83 views

Using upper bound information in graph search

I am using A* (A-Star) to search a graph. A* algorithm takes advantage of the information $h(x)$, which is a lower bound of the distance between a vertex $x$ and the destination vertex. In other ...
2
votes
2answers
122 views

About the roots of the matching polynomial

Can someone kindly give me an expository reference on matching polynomial and its roots? (there is a proof that they are always real?) I saw these two related discussions, Roots of matching ...
2
votes
0answers
71 views

Are there two-sided $\varepsilon$-expanders with independent sets of size $(1-\varepsilon)n$?

Terry Tao's notes on expander graphs has the following exercise: Exercise 13 Let $G$ be a $k$-regular graph on $n$ vertices that is a two-sided $\epsilon$-expander for some $n > k \geq 1$ and ...
1
vote
1answer
215 views

Probability of connected graph on torus

Let $G = (V, E)$ be a graph on n vertices constructed in the following way: Each vertex $v \in V$ is positioned uniform randomly in $[0, 1] × [0, 1]$. Connect two vertices $u, v \in V$ if $d(v,u) ≤ ...
2
votes
0answers
53 views

Fixing (non)-independency of a the subfamilies of finitely many events.

I'm would be interesting in any construction of a probability space with n events (n is given), where for every subset of these events, it is also given whether or not, the family is mutually ...
1
vote
0answers
55 views

clustering in a graph on boolean functions

Fix some n and k. Consider the following directed graph: vertices are all functions $2^n\rightarrow 2^n$ and a vertex f has an edge to a vertex g for every h such that $f=h\circ g$ and h depends only ...
3
votes
2answers
314 views

Find all faces in a graph from list of edges

I have the information from a undirected graph stored in a 2D array. The array stores all of the edges between nodes, e.g. graph[3] might be equal to [1,8,30] and represents the fact that node 3 ...
3
votes
2answers
330 views

Graph game minimum vertex degree

Consider the following graph game, given a graph $G=(V,E)$ on $n$ vertices with minimum degree $ \gg \log(n)$. Players are BR and MA (BR moves first): BR claims an unclaimed edge from $E$, adds it ...
2
votes
1answer
319 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 ...
5
votes
3answers
134 views

Minimize distance between centroids of subsets of points

In a n-dimensional space, I want to divide a set of m points into v (non-empty) subsets. I want to minimize the sum of the pairwise Euclidean distances between the centroids of the resulting subsets. ...
3
votes
1answer
301 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 ...
-1
votes
1answer
53 views

How to construct a semi-positive definite matrix in this form: (L=D-A')

As known, the graph Laplacian $L = D - A$ is semi-positive definite. What if there is a matrix $A'$ where $$ A'_{ij} = \begin{cases} A_{ij}, \quad if A_{ij} >0 \\ -\varepsilon, \quad if A_{ij} = ...
3
votes
1answer
134 views

Existence of subgraphs when given its degree sequence

For a given simple graph $G$ with $n$ vertices $v_1,v_2,\dots v_n$, the corresponding degree sequence is $d_1,d_2,\cdots,d_n$. My qusetion is: How to determine whether there exist subgraphs in $G$ ...
4
votes
0answers
189 views

Navigation in a graph

The problem Let $G=(V,E)$ be a graph. $k = O\left(\log(|V|)\right)$ distinct vertices are picked randomly from $V$. We call the set of chosen $k$ vertices $T$. Assumptions about the graph: You may ...
0
votes
0answers
186 views

A question about Assaf Naor's review in Bourbaki about the Batson-Spielman-Srivastava result

I am referring to this article - http://www.cims.nyu.edu/~naor/homepage%20files/Exp.1033.pdf If I understand right, the author states that his equations (8) and (9) are equivalent to the equations ...
3
votes
1answer
188 views

Meaning of eigenvalue 1 and symmetry in Laplacian spectra of graphs

We often see normalized Laplacian spectra of graphs where density on eigenvalue 1 serves as an axis of symmetry, with particularly high (blue spectra in the figure) or low densities (red spectrum) ...
2
votes
1answer
66 views

Visibility kernels of embedded graphs

Let $G$ be a connected graph embedded in the plane with all edges straight segments. For $\alpha \in (0,\pi)$, define an $\alpha$-path as a path in $G$ with all turns at vertices within ...
2
votes
1answer
73 views

How to infer missing nodes from a path?

I have a first data set which is a list of train stops with coordinates (lat, lon), but not the "links" between the nodes/stops (this could thought of as a null or empty graph). I have a second data ...
0
votes
0answers
34 views

Number of graphs with n vertices and k edges up to isomorphy [duplicate]

Is there a way to figure out the number of individual graphs with n vertices and k edges up to isomorphy? I'm particularly looking at graphs with: n = 25, k = 50 n = 50, k = 170 n = 100, k = 700
1
vote
0answers
42 views

Recognizing bridgeless cubic graph with special 2-factor

A 2-factor of graph $G(V, E)$ is a set of vertex-disjoint cycles that cover $V$. It is known that every connected bridgeless cubic graph contains a 2-factor (and a perfect matching). I conjecture ...
2
votes
0answers
79 views

What is the significance of the median eigenvalue?

When I look at the spectral density plots of my (usual) laplacian graphs, they spike at the median eigenvalue. But what significance for the graph/matrix (which originates from a network) does the ...
0
votes
0answers
22 views

Is there effective algorithm for finding “minimal discovery time” for large graphs?

Consider a large, probably sparse graph with Markovian random walkers on it. Define discovery time as time to first reach a vertex by random walk from uniform start. Are there effective ways to find ...
6
votes
0answers
125 views

What is known about the chromatic number for minimum-distance graphs in higher dimensions?

For a set of points in $\mathbb{R}^d$ with minimum distance $a$, the minimum-distance graph connect two points iff they are at distance $a$. We can also view it as the tangency graph for a set of ...
2
votes
1answer
108 views

Connections between loops (algebraic structure) and graphs

I would like to know whether there are known constructions which provide a bijection between loops (isomorphism classes) and (possibly directed) graphs. Any reference to a useful paper in this ...
8
votes
3answers
522 views

Separating points in the plane II

Let A be a set of $2m$ points on the plane so that no open set of diameter $2$ has more than m of them. Define $A+A+...+A$ ($k$ times) to be the multiset of $k$-sums from $A$. That is, we consider all ...
4
votes
0answers
86 views

Actions of amenable groups on graphs with uncountably many ends

Let $G$ be a finitely generated amenable group acting transitively on an amenable Schreier graph $S$. Is it possible for $S$ to have uncountably many ends? An amenable graph with uncountably many ends ...
2
votes
1answer
89 views

Is a rigid cycle a chordal graph?

There are two relevant questions: (1) We know an edge set $C$ is a rigid cycle in $\mathcal{G}_2(n)$ if and only if $|E(C)|=2|V(C)|−2$ and $|F|≤2|V(F)|−3$ for every proper subset $F$ of $E(C)$. Thus, ...
0
votes
2answers
113 views

Form of the Shannon capacity for Heptagon?

Is the $0$-error capacity of $7$-cycle: $(1)$ known to be of form $7^q$ for some $q\in \mathbb Q$?
1
vote
0answers
81 views

How to restructure adjacency matrix $A$ from shortest distance matrix $B$ in Network topology inference

An undirected graph with $n$ nodes could be referred to as an adjacency matrix $A$. $A=[a_{ij}]_{n×n}$ with $a_{ij}=a_{ji}=1$ standing for there being an edge between node $i$ and node $j$, and no ...
2
votes
0answers
129 views

Connected graph as connected space

Let $G$ be locally finite graph. By $|G|$, we mean the Freudenthal compactification of the 1-complex $G$, see chapter 8 of "Graph Theory" by Diestel. It is followed from Lemma 8.5.4 of Diestel's book: ...
6
votes
2answers
322 views

Who first used/gave a coordinate representation of a graph?

In his proof of the Shannon capacity of a graph, Lovasz utilizes a coordinate representation of the pentagon (namely an orthonormal representation). Who first utilized a coordinate representation for ...
0
votes
2answers
111 views

Coloring of a normal map

can the following proposition be proved? If so please suggest a method. Can Kempe’s Argument be used for proof ? Proposition: A normal map has a colouring of countries by 4 colours iff the edges of ...
4
votes
2answers
149 views

eigenvalue estimate of the adjacency matrix

The adjacency matrix of a nonempty (undirected) graph has a strictly positive largest eigenvalue $\lambda_\max$. A very easy upper estimate for it can be obtained directly by Gershgorin's theorem: $$ ...
2
votes
0answers
84 views

Minimum number of perfect matchings in a regular bipartite graph

Is there a lower bound on the number of perfect matchings in a $k$-regular bipartite graph? One can use Hall's marriage theorem and induction on $k$ to derive the lower bound of $k$. I can't come up ...
1
vote
1answer
99 views

Finding a sufficiently large complete bipartite subgraph using matrix counting

I'm trying to reconstruct the proof using matrix counting that there exists two subsets $A,B$ of $\{1,\cdots,N\}$ with $\#A=\#B$ such that for any $a\in A$ and $b\in B$, $a+b$ is prime, and $\#A=\#B$ ...
3
votes
0answers
99 views

Counting Problems where Labeled is Known but Unlabeled is Not

Cayley's formula states that the number of labeled trees on $n$ vertices is $n^{n-2}$. There are many nice proofs of this compact formula. To contrast, counting unlabeled trees is considerably ...
1
vote
3answers
177 views

Is there a formula for the number of labeled forests with $k$ components on $n$ vertices?

Cayley's formula states that the number of labeled trees on $n$ vertices is $n^{n-2}$. My question is: Is there a generalization of this formula for forests? Let $f_{n,k}$ denote the number of ...
1
vote
2answers
61 views

Coloring maximal independent sets with 1 color

Let $G$ be a graph and $M\subseteq V(G)$ be a maximal independent set. Is there a coloring $c:V(G)\to\chi(G)$ such that $c$ is constant on $M$? (The answer is positive for graphs with infinite ...
1
vote
1answer
121 views

Difference between modularity and clustering in graphs

The definition of modularity given on wikipedia is as follows. http://en.wikipedia.org/wiki/Modularity_(networks) Modularity is one measure of the structure of ...