**2**

votes

**0**answers

220 views

### Group of local complementation as a coxeter group

Can the group generated by local complementations, ${lc_i|i=1,\cdots,n}$ on simple graphs on $n$ vertices, be categorized as a coxeter group? After all these obey:
\begin{equation}
\langle lc_i| ...

**2**

votes

**0**answers

131 views

### finding set of tree decompositions to cover all pairs of vertices

I first asked this on cstheory.SE but got no reply.
Let $P(X_i=x)$ represent probability that randomly chosen proper $q$-coloring of an $L\times L$ square grid contains color $x$ at position $i$. How ...

**2**

votes

**0**answers

166 views

### Semantics of neural network-like structures

Background
Language (of mathematicians and most other people) has a sequential surface structure and a tree-like deep structure. So semantics usually is the semantics of such syntactical structures: ...

**2**

votes

**0**answers

258 views

### Drawing a combinatorial 3-configuration of points and lines with pseudolines

This question is related to the question of drawing a combinatorial 3-configuration of points and lines with straight lines. We only relax the condition and admit drawings with pseudolines. Let us ...

**2**

votes

**0**answers

201 views

**1**

vote

**0**answers

71 views

### Disks in Flat Embeddings of Graphs in $\mathbb{R}^3$

Robertson, Seymour and Thomas proved that any linkless graph $G$ has a flat embedding in $\mathbb{R}^3$ (see for example A survey of linkless embeddings). An embedding of $G$ is flat if for any cycle ...

**1**

vote

**0**answers

49 views

### Possible ways to create a graph representation from a distance matrix (through approximation)

Forgive me, Im not math professional, but a computer scientist at the beginning of my base research from my thesis, so bare with me if I miss something blatantly obvious.
I have a Euclidean distance ...

**1**

vote

**0**answers

53 views

### Programmatically recognizing symmetries of a polyhedron

I asked this question on MSE a month ago, but nobody was able to answer it, so I guess the question is more difficult than I initially thought: ...

**1**

vote

**0**answers

92 views

### Kempe chain color swaps in a partially colored map

Crossposted from math.stackexchange.com:
http://math.stackexchange.com/questions/904932/kempe-chain-color-swaps-in-a-partially-colored-map
Question: In this partially Tait's colored map, using ...

**1**

vote

**0**answers

72 views

### Empty node in cactus construction

Is there a necessary condition for not having empty node in the construction of the cactus of the minimum cuts of a graph?
In particular is there a necessary condition for not having empty k-junction ...

**1**

vote

**0**answers

105 views

### Find a path that covers as many nodes as possible

I have the following interesting problem. Given a graph $G$, an agent starts to mark nodes in $G$ in the following way: it marks all nodes within distance $d$ from it. Now the question is to find the ...

**1**

vote

**0**answers

47 views

### Simulation of disassortative random graphs

Recently I have been trying to find a succinct algorithm for generation of disassortative networks. The best I have found is the algorithm by Newman described in his paper "Mixing patterns in ...

**1**

vote

**0**answers

51 views

### Polynomial problems in graph classes defined by forbidden induced cyclic subgraphs

Let $C$ be a graph class defined by a finite
number of forbidden induced subgraphs, all
of which are cyclic (contain at least one cycle).
Are there graph problems that can be solved in
...

**1**

vote

**0**answers

52 views

### Asymptotic results in unbalanced left $d$-regular expander graphs

Let $U = [n]$ and $V = [m]$ be sets of nodes with $n > m$ and $E = U\times V$ be a set of edges. Let $\mathcal{N}(S)$ be the set of neighbors of a subset $S$ from $U$ or $V$.
Call a graph $G = (U, ...

**1**

vote

**0**answers

66 views

### labeling vertices in a graph to minimize distance between adjacent vertices

We have a regular graph $G$ of degree $m$ on $n$ vertices and we label each of its vertices with the number $1$ through $n$. What can we say about the maximum difference between the numbers of two ...

**1**

vote

**0**answers

112 views

### Relationship betwen eigenvectors

Suppose that we have two matrices A and B. Matrix B is taken from A with one row and one column deleted. On the other hand A is n*n matrix and B is (n-1)*(n-1) matrix and is created by deleting last ...

**1**

vote

**0**answers

122 views

### Basis of periodic tiling of Wang tile

Given a set of Wang tile,
Given 3 periodic tiling: A, B, C
We define 3 vector F[A], F[B], F[C]
each vector correspond to the appearing frequency of each type of tiles in the tiling.
Now, we ...

**1**

vote

**0**answers

84 views

### What is the projective dual of a planar graph?

Everybody learns the usual definition of the dual of a planar graph when edges are preserved and faces are mapped to vertices. Everybody learns the projective duality. What if we apply it to a ...

**1**

vote

**0**answers

42 views

### Euclidean embedding of a graph based on 1-ring neighborhood distances only

Consider a graph $(V,E)$, $\vert V \vert = n$ and weights $\{l_{ij}\}$, where $l_{ij}>0$ iff there is an edge connecting vertices $v_i$ and $v_j$. Distances beyond the 1-ring neighborhood are not ...

**1**

vote

**0**answers

63 views

### Recovering Spherical Harmonics from Discrete Samples

Consider a collection of $N$ points on the 2-sphere chosen uniformly at random. Let's say that there's an edge between two such vertices if their geodesic distance is less than $r_N$. The resulting ...

**1**

vote

**0**answers

56 views

### Disconnecting a three regular graph

Setting, a random three regular graph. If I start removing edges, what's the probability that I disconnect it? What I know is that if I disconnect a graph I get a subgraph, and that the expected ...

**1**

vote

**0**answers

128 views

### Knight's metric: ellipse and parabola

Knight's metric is a metric on $\mathbb{Z}^2$ as the minimum number of moves a chess knight would take to travel from $x$ to $y\in\mathbb{Z}^2$. What does a parabola (or an ellipse) became with this ...

**1**

vote

**0**answers

64 views

### interpretation of generalized eigenvalue/vectors in spectral graph theory

Let us say I have a symmetric graph adjacency matrix A, a degree matrix D, a laplacian L (D-A). I have a generalized eigenvalue equation $Av=\lambda Lv$. Does the eigenvalue/vectors produced in this ...

**1**

vote

**0**answers

31 views

### Harmonic Bergman spaces on graphs

Harmonic Bergman spaces on Euclidean domains are a set of harmonic functions on a domain that are from $L^{p}$ of that domain. I tried to find something on harmonic Bergman spaces on graphs because we ...

**1**

vote

**0**answers

50 views

### Perfect Matchings in Biclique Decompositions of Multigraphs

Suppose you have the $K_{2n}$ covered by a multigraph consisting of $2n-1$ bicliques, each consisting of a partition of the vertex set into two sets of equal size.
Here is a picture of $K_{6}$ with 5 ...

**1**

vote

**0**answers

89 views

### On 'Very Movable' Geometric Configurations (Configurations with a large degree of freedom)

Let $C$ be an $(n_r, b_k)$ combinatorial configuration that admits a geometric realization in the plane. I'm interested in the maximum number of points/lines $M$ of $C$ we can place in general ...

**1**

vote

**0**answers

132 views

### A connection between nonplanar complete graphs and the alternating group?

I didn't get any response on MSE so I though I'd give this a try here (my question on MSE).
I went to an undergrad's senior honors thesis presentation a while ago. She was discussing crossing numbers ...

**1**

vote

**0**answers

143 views

### Can assigment of Cayley graphs be functorial?

Let $G$ and $G'$ be finitely generated groups and $f:G\to G'$ a homomorphism. First question: for a given $f:G\to G'$ it possible to select generating sets $S\in G, S'\in G'$ so that their would be a ...

**1**

vote

**0**answers

42 views

### complexity of in-dominating set

Is the decision problem In-Dominating Set NP-complete for digraphs of regular out-degree (greater than (n-2)/4, in particular)? I'm mainly looking for the reference.
Thanks for any answer!

**1**

vote

**0**answers

71 views

### How close to platonic can a non-platonic planar graph be?

Direct question:
Is it possible to construct a finite, planar, $k$-regular graph in which all the faces except one have the same degree (are bounded by a cycle with the same number of edges), and the ...

**1**

vote

**0**answers

88 views

### Capacity of Cycle Graphs

Shannon capacity $\Theta(G)$ of pentagon is achieved at $2$-fold strong product of the pentagon.
It is also known that the Lov\'asz theta $\vartheta(G)^m\neq\alpha(G^{\boxtimes m})$ for any finite ...

**1**

vote

**0**answers

131 views

### Is the automorphism group of a homogeneous (locally finite) tree unimodular?

I have seen somewhere (that I don't remember now) that the (full) automorphism group of a k-regular tree is unimodular. I assume a k-regular tree is the same thing as the homogeneous tree of degree k ...

**1**

vote

**0**answers

102 views

### A traveling time problem

Given any undirected, connected and simple graph $G(V,E)$,each node of which is considered as a city. We call $j$ a neighbor of $i$ if $(i,j)\in E$. $N_i$ is the set of neighbors of $i$. $|V|=N$
...

**1**

vote

**0**answers

107 views

### When does the induced directed graph of a directed multigraph preserve information?

Let G be a directed multigraph, and let H be the induced directed graph whose vertices are the edges of G, and whose edges are given by pairs of consecutive edges in G; i.e., there is an edge from v ...

**1**

vote

**0**answers

668 views

### What is a good algorithm to measure similarity between two dynamic graphs?

I am using graphs to represent structure present in a scene. The vertices represent the objects in the scene and the edges represent the relationship between two nodes(touching, overlapping, none). ...

**1**

vote

**0**answers

127 views

### What is the expected Cheeger constant of a random graph?

Recall that the Cheeger constant (AKA isoperimetric constant) of a graph $G$ is the infimum of $\frac{\partial S}{vol S}$ over all subsets $S$ of $G$ with volume no larger than $vol(G)/2$. I would ...

**1**

vote

**0**answers

72 views

### Terminology question: maximal non-branching directed paths

Is there any special word for a maximal non-branching directed path in a network or diforest?
To be 100% precise, by "maximal non-branching directed path" I mean a path $P=x_1,x_2,\ldots$ (maybe ...

**1**

vote

**0**answers

114 views

### “Stable” bounds on maximum size independent set in a graph

Suppose we have a graph $G=(V,E)$, and we want to upper bound $|I|/|V|$, where $I$ is the largest independent set in $G$. Then there is the Hoffman bound, which is $|I|/|V| \leq ...

**1**

vote

**0**answers

64 views

### Details about Kelman's equivalent form of Barnette's conjecture

Barnette's conjecture states that every cubic planar bipartite 3-connected graph admits Hamiltonian cycles.
Kelman claims that this conjecture is equivalent to a stronger one, which imposes some ...

**1**

vote

**0**answers

65 views

### Effect of removing a Hamiltonian cycle on the Laplacian spectrum

Notation: $\lambda_{\max}(G)$ is the largest eigenvalue of the Laplacian matrix of the graph $G$ (aka the Laplacian index of $G$).
Now suppose $G$ is a Hamiltonian graph with Hamiltonian cycle $C$.
...

**1**

vote

**0**answers

149 views

### Self-modelling structures

Consider - for the sake of simplicity - only graphs as structures.
For undirected graphs $(V, E\subseteq \binom{V}{2})$ let
$E(v)$ be the set of edges $e\in E$ incident with $v$, i.e. $\lbrace e ...

**1**

vote

**0**answers

65 views

### Second eigenvalue of a weighted tree

Hello,
I am interested in upper bounding the second largest eigenvalue of the adjacency matrix of a graph $T$ with the following property:
1. $T$ contains self loops.
2. $T$ contains multiple edges ...

**1**

vote

**0**answers

120 views

### Recovering a partition from spectral properties of the graph Laplacian

Let $G$ be a weighted graph with vertices $V$. Let $W$ be its real-valued, non-negative, $|V|\times|V|$ adjacency/affinity matrix. Let $L = \mathrm{diag}(W\mathbf1)-W$ be the (unnormalized) graph ...

**1**

vote

**0**answers

60 views

### Can this application of the moment closure method to epidemics on networks be made rigorous?

Short version: Consider the SI model of infectious disease spread on a random graph $G$ with a given degree sequence. Let $j$ be a vertex and let $i$ and $k$ be two of its neighbors. If $G$ ...

**1**

vote

**0**answers

57 views

### shortest path in undirected graph in LogSpace

Given an undirected graph G (can be cyclic) with the promise that all its faces have 3 sides is it possible to find the minimum distace between a source and any other vertices in LogSpace or in ...

**1**

vote

**0**answers

71 views

### Number of edges in graph in terms of reliability

Consider a connected graph $G$ with min-cut $c$. Suppose the edges fail (are removed) independently with probability $p$. Then $U(p)$, the probability that $G$ becomes disconnected, is at least $p^c$. ...

**1**

vote

**0**answers

92 views

### Schönhage's SMM with only one instruction

It is possible to implement $\lambda$-calculus in Schönhage's storage modification machine using an infinite set of nodes and one single program consisted exclusively of (about hundred) instructions ...

**1**

vote

**0**answers

89 views

### Set of upper bounds is finite for any finite subset

Is there a term to describe a preordered set $P$ in which any finite subset $S \subset P$ has at most finitely many minimal upper bounds? The preordered sets I'm studying generally aren't ...

**1**

vote

**0**answers

108 views

### Turing-complete primitive interaction systems

Let us call primitive an interaction system with the signature
$\Sigma = \{(\rho, 0), (\xi, n)\}, \quad n \geq 2;$
and the only rule being of the form
$\rho \bowtie \xi[\rho, \xi(a_1, \dots , a_n), ...

**1**

vote

**0**answers

118 views

### regular hyper graph construction

Is there any algorithm to generate 3-uniform k-regular hypergraph with n vertices?? Any help is appreciated. Thanks.