Tagged Questions

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
61 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
29 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 ...
-3
votes
0answers
51 views

Mathematically compute - species diversity [on hold]

Using a simple model, and having these as paramters numberofspecies <- 100 meaninitialpopulationsize <- 50 sdloginitialpopulationsize <- 1 #determines variation in initial population ...
1
vote
0answers
42 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 ...
2
votes
2answers
175 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
125 views

Graph game minimum vertex degree

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

Question regarding Grid Graph [on hold]

Let $T_{n^{2}}$ denote the grid $T_{n^{2}}=\{(j,k): 1\leq j \leq n,1 \leq k \leq n\}$. Given a grid graph $G=(V,E)$ with vertices $V \subseteq T_{n^{2}}$ and ...
3
votes
1answer
120 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 ...
0
votes
0answers
19 views

Adding an edge to a MST generated from a distance matrix [on hold]

Given an N×N distance matrix, but not an adjacency matrix for a connected, weighted, undirected graph G, I've managed to find a minimum spanning tree (with N−1 edges) using Prim's algorithm. Now I ...
-1
votes
1answer
40 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
83 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
163 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
145 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
99 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
93 views

state-of-the-art graph theory libraries like LEDA [on hold]

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
60 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
53 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
1answer
68 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
30 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
31 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
65 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
19 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
93 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
89 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
502 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 ...
2
votes
0answers
71 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
56 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
79 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
46 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
13 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
122 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
299 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
69 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
87 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
66 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
86 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
77 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
106 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
237 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
56 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
119 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
113 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 ...