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

0
votes
0answers
68 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
0answers
46 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) ...
1
vote
0answers
68 views

state-of-the-art graph theory libraries like LEDA

I came across LEDA (library of efficient data types and algorithms) which implements graph theory algorithms: http://www3.cs.stonybrook.edu/~algorith/implement/LEDA/implement.shtml I want to ask: ...
2
votes
1answer
33 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 ...
1
vote
0answers
48 views

The number of blocks in Szemerédi Regularity Lemma

In mathematics, the Szemerédi regularity lemma states that every large enough graph can be divided into subsets of about the same size so that the edges between different subsets behave almost ...
-2
votes
0answers
86 views

Arranging books into bags [on hold]

I'm trying to find an algorithm to answer the following question (informal): given a (finite) set of distinct books of different (positive integer) sizes and a (finite) set of bags of different ...
1
vote
0answers
24 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
29 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
25 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
61 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
18 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
89 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 ...
1
vote
1answer
88 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
452 views
+50

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 ...
2
votes
0answers
69 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 ...
1
vote
0answers
55 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
77 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
votes
0answers
45 views

Characterization of a family of interval graphs

Let $G=(V,E)$ be a graph, where $V$ is a set of integral intervals from $[1,n]$ and $\left \{i,j \right \} \in E$ if $i \cap j \neq \emptyset $. Is the family of these graphs a proper subset of the ...
1
vote
0answers
12 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
121 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
296 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
68 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 ...
3
votes
2answers
82 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
65 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
83 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
76 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
93 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 ...
0
votes
2answers
42 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
31 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 ...
2
votes
1answer
101 views

Directed Minimal Cuts in a DAG

I'm looking for information about minimal directed cuts (dicuts) in (connected) DAGs (directed acyclic graphs). A dicut in a directed graph, is a cut $(P_1,P_2)$ in which all edges in $E(P_1,P_2)$ ...
1
vote
0answers
100 views

lower bound for difference between max cut and min cut

Let $G=(V,E)$ be a graph on $n$ vertices with edge weights $w=(w_e)_{e\in E}$. Let $M^+$ and $M^-$ be the maximum and the minimum cut values, i.e. ...
5
votes
4answers
234 views

Do there exist sparse graphs with large crossing number?

Does there exist a sequence of graphs $\{ G_n \}$ such that $G_n$ has $n$ vertices, the number of edges of $G_n$ is $O(n)$, and the crossing number of $G_n$ is $\Omega(n)$? In particular, do ...
5
votes
0answers
54 views

Independent domination number for grid graphs

Let $G_{n,m}$ be the $n \times m$ grid graph, i.e. $G= P_n \Box P_m$, and $T_{n,m}$ the $n\times m$ torus grid graph, i.e. $G= C_n \Box C_m$, where $P_n$ and $C_n$ indicate the path graph of length ...
4
votes
1answer
112 views

Expectation of ratio of functions of i.i.d. Bernoullis: a concentration question

Consider the following $n \times n$ symmetric matrix of i.i.d. Bernoulli random variables, $X_{ij}$. For $i=1,...,n$ and $i<j\le n$. Let $X_{ij} \sim \text{Bernoulli}(p)$ when $i \ne j$ ($p$ ...
1
vote
2answers
70 views

Regular graphs with strongly regular edge colorings

Given a positive integer $c>1$, for what parameters $(v,k,\lambda,\mu)$ does there exist a $c k$ regular graph on $v$ vertices that can be given an edge coloring with $c$ colors, such that the ...
1
vote
1answer
86 views

Can we count isospectral graphs?

On n-vertices, how many isospectral graphs exist? [..I saw this previous "historic" discussion between two of the stalwarts in this field - Operation on Isospectral graphs ] Given a graph are ...
6
votes
2answers
110 views

Number of edges in linklessly embeddable graphs

Consider graphs over $n$ nodes. What is the maximum number of edges of a linklessly embeddable graph? A more general question is the following. Given $\mu$ what is the maximum number of edges of ...
3
votes
0answers
119 views

What do we know about isospectral Cayley graphs?

Let $\Gamma_1=\Gamma_1(G_1,S_1)$ (respectively $\Gamma_2=\Gamma_2(G_2,S_2)$) be a Cayley graph for the group $G_1$ and the finite generating set $S_1$ (respectively $G_2$ and the finite generating set ...
0
votes
0answers
49 views

Induced subgraphs on a Laminar family of vertices with constant diameter

$X$ is a family of subsets of $V$. $X$ is called a Laminar family on $V$ if for all $A,B\in X$, either $A\cap B=\emptyset$, $A\subset B$ or $B\subset A$. Let $X$ be a family of subsets of $V$. A ...
0
votes
1answer
66 views

Paper on unit disk graphs

I was wondering if anybody knows of a 'link' to the paper by Marathe 1995 et al on analysis of the greedy algorithm for finding a Max independent set in Unit Disk Graphs?
2
votes
0answers
28 views

“drift” of a random graph $G(n,p)$ with $p=\alpha\ln{n}/n$

Suppose $G\sim G(n,p)$ with $p=\alpha\ln{n}/n$ for some large constant $\alpha$. I wish to show a certain "drift" property of $G$, which can roughly be phrased as follows: if $u$ is "not that far" ...
1
vote
1answer
53 views

Coloring algorithm maximising color difference between neighbors

Consider a graph and a set of ordered colors ${\cal C} = \{1,2,\cdots,C\}$. I want to color each node $i$ with a color $c_i\in{\cal C}$ so as to maximize the minimum color difference between two ...
2
votes
4answers
261 views

Algorithm to find the “optimal” path in a given graph

Assume that $G=(V,E)$ is an undirected connected graph and that $H: V \to \mathbb R$ is a function that assign at each vertex $v \in V$ its height $H(v)$. Think of the pair $(G,H)$ as an energy ...
2
votes
1answer
74 views

Existence of neighborhood inclusion for 4-chordal graphs

Let $N(v)$ be the (open) neighbourhood set of a vertex $v$, and let $N[v]$ be the closed neighbourhood set of $v$. A graph $G$ is called 4-chordal if $G$ has no induced cycle with five or more ...
2
votes
3answers
510 views

a colouring / matching problem

While trying to find a bijection which preserves various combinatorial statistics, I was led to the problem below. Very much to my surprise, a closely related question, Coloring summands of given ...
0
votes
1answer
168 views

Coin graph is 4-colorable

How can we prove that a coin graph is 4-colorable???Also, can we find any example of an non-3-colorable coin graph.
3
votes
1answer
89 views

Independent Sets in random geometric graphs

I was wondering if a lot is known about independent sets in Random Geometric graphs? Most google searches don't bring up much. In addition I'm interested in any algorithms used for finding independent ...
1
vote
2answers
128 views

Non-DS circulant graphs

Let $p$ be a prime number greater than or equal to 11. Are there any cospectral non-isomorphic graphs with circulant graphs on $p$ vertices. Which circulant graphs over prime number of vertices ...
2
votes
0answers
44 views

Weighted graph similarity

I have the following problem. Consider an undirected biconnected graph with $n$ vertices and $m$ edges ($n \leq m \leq n(n-1)/2$). The $m$ edges of the graph are then "populated" by integer weights ...
2
votes
1answer
188 views

On the maximum number of $t$-subset of $\{1,\ldots, n\}$ having pairwise singleton or empty intersections

Let $n$, $t \in \mathbb N$ two natural numbers such that $0<t<n$, and let $A$ be a set of $n$ elements. We call a quasi-partition or q-p of $A$ a subset $W \subset \mathcal P(A)$ such that we ...