# Tagged Questions

**-2**

votes

**0**answers

43 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

**0**answers

20 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

**0**answers

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

**0**answers

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

**0**answers

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

**0**answers

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

**0**answers

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

**1**answer

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

**3**answers

418 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

**0**answers

68 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

**0**answers

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

**2**answers

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

**0**answers

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

**0**answers

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

**0**answers

120 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

**2**answers

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

**2**answers

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

**2**answers

81 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

**0**answers

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

**1**answer

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

**0**answers

75 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

**3**answers

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

**2**answers

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

**1**answer

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

**1**answer

97 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

**0**answers

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

**4**answers

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

**0**answers

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

**1**answer

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

**2**answers

69 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

**1**answer

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

**2**answers

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

**0**answers

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

**0**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**4**answers

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

**1**answer

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

**3**answers

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

**1**answer

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

**1**answer

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

**2**answers

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

**0**answers

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

**1**answer

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

**4**

votes

**0**answers

69 views

### Subgraphs of planar trivalent graphs

Let's think about planar trivalent graphs. (Or you can dualize and think about triangulations if you prefer.) It's easy to come up with a list of 'planar trivalent graphs with boundary' such that at ...

**1**

vote

**2**answers

113 views

### Minimum number of unlabeled planar graphs

Does anybody know if there is any research on a lower bound on the number of (non-isomorphic) unlabeled planar graphs with maximum node degree $d$?
Alternatively, a lower bound on the number of all ...

**-4**

votes

**1**answer

56 views

### Survey on Hypergraph Theory [closed]

I want to learn about hypergraphs.Can anyone help me with some links, articles and surveys.
Thanks

**3**

votes

**0**answers

74 views

### More 3-connected cubic graphs with all 2-factors of same cycle type?

The setup is as in this question: Let $G$ be a 3-connected cubic graph. If all 2-factors of $G$ are isomorphic (as graphs), i.e. all have the same partition $\pi$ as cycle type, we'll say that $G$ is ...

**2**

votes

**0**answers

56 views

### Problems Solvable/Decidable by Counting Shortest Paths in Graphs

This questions is based on a dispute, whether it would be possible to calculate 'nice' routes in Manhattan, if the road network is assumed to be a rectangular grid and, that 'nice' means that there is ...