**5**

votes

**0**answers

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

**5**

votes

**0**answers

157 views

### (Connected) Cayley graphs of PSL(2,q) from (2,3,n)-triples

Let $G = PSL(2,q)$. I'm interested in the Cayley graphs of $G$ generated by triples $(A,BAB^{-1},B^{-1}AB)$, where $A, B \in G$ are elements of order $2, 3$ respectively: such a triple generates all ...

**5**

votes

**0**answers

80 views

### Mapping graphs to ordinals

Robertson-Seymour theorem implies that graph minor relation is a well-quasi-ordering, which means (among other things) that this relation can be extended to a well-order, and other result says that ...

**5**

votes

**0**answers

99 views

### Monotone embedding of complete binary tree in hypercube

Embedding different graphs, especially binary trees, in the hypercube has a huge literature. However, I could not find anything if we restrict the embedding to be monotone. So I would like to ...

**5**

votes

**0**answers

151 views

### Are the roots of chromatic polynomials plus a fixed constant dense in $\mathbb{C}$?

Alan Sokal proved that chromatic roots are dense in the whole complex plane. I.e., if $P(G;z)$ denotes the chromatic polynomial of a finite simple graph $G$ evaluated at $z \in \mathbb{C}$, then ...

**5**

votes

**0**answers

83 views

### Implementations of Tutte polynomial [reference request, of a kind]

This question is not a 100% fit for MO, but it is a serious question that can be viewed as a sort of reference request, and I think fits here more than elsewhere.
I have been asked to write a chapter ...

**5**

votes

**0**answers

113 views

### Complexity of finding three perfect matchings with no edge in common in a bridgeless cubic graph

According to a conjecture:
Conjecture (Fan & Raspaud, 1994) Every bridgeless cubic graph contains three perfect matchings with no edge in common.
Equivalent statement here
Main question:
...

**5**

votes

**0**answers

165 views

### A linear optimization problem on a graph

Let $G=(V,E)$ be a finite graph and let $f$ be any positive function defined on the vertices. Put weights on the vertices $v_{i}$, way $w_{i}$ so that $\sum_{i=1}^{n}w_{i}\leq 1$. Assume that every ...

**5**

votes

**0**answers

145 views

### Graphs with many positive eigenvalues of their distance matrix

Let $G$ be a simple connected graph $D(G)$ its distance matrix and $n_{+}(G), n_{-}(G)$ the number of positive and negative eigenvalues of $D(G)$ respectively.
We call a graph $G$ optimistic if ...

**5**

votes

**0**answers

145 views

### Diameter of subset sum graph

We have a finite set $X$, a weight function $w: X\rightarrow \mathbb{Z}^+$, and constants $k\leq c\in\mathbb{N}$.
Let the weight $w(S)$ of a set $S\subseteq X$ be the sum of the weights of its ...

**5**

votes

**0**answers

95 views

### making a graph well-covered without changing its Shannon capacity

This strongly relates to an earlier question of mine.
Let $G$ be a graph, $\alpha(G)$ its independence number and $\Theta(G)$ its Shannon capacity.
Question: can one 'add new vertices' to $G$ such ...

**5**

votes

**0**answers

125 views

### How does the number of self-avoiding paths between two points scale, in a square/cubic lattice?

Consider two different infinite graphs, whose vertices are drawn from $\mathbb Z^2$ or $\mathbb Z^3$. Let $P_d : \mathbb Z^d \times \mathbb N \to \mathbb N$ for $d \in \{2,3\}$ be the function such ...

**5**

votes

**0**answers

149 views

### When can the Cheeger constant be well-approximated by ``Hamming balls''?

Given a graph G, the Cheeger constant is defined by
$$
\DeclareMathOperator{\Vol}{Vol}
h_G := \min_{S \subseteq V, \Vol S \leq (\Vol G)/2} \frac{|\partial S|}{\Vol S}.
$$
Here, $\Vol S$ is the sum of ...

**5**

votes

**0**answers

277 views

### Sequence of graphs with small $\lambda_1$ (the smallest nonzero eigenvalue of a regular finite graph)

The combinatorial laplacian on a finite graph $G$ can be defined as $ \Delta: \mathbb{C}^G \to \mathbb{C}^G$ sending the function $f:G \to \mathbb{C}$ to $(\Delta f)(v) = \sum_{v' \sim v} \big( ...

**5**

votes

**0**answers

230 views

### Any approximation algorithms for self-avoiding walks?

I've a graph whose edges are weighted by probabilities, perhaps all equal. I would like to compute the overall probability of traveling between vertices x and y in the graph after I delete each edge ...

**5**

votes

**0**answers

396 views

### “sum over labelings” representations of graph polynomials

It seems that there's a general way to go from "recursive" definition of a graph polynomials to "subset expansion" formulas.
Furthermore, polynomials with subset expansion formulas often have a ...

**5**

votes

**0**answers

586 views

### Counting graphs whose vertex induced subgraphs are members of a fixed set

Let $C$ be the class of graphs of girth $g$ or more. $C$ can alternatively be characterized as: $G \in C$ iff each of $G$'s vertex induced subgraphs on less than $g$ nodes is a forest.
We can ...

**5**

votes

**0**answers

422 views

### Natural models of graphs?

Motivation
I want to capture the notion of natural models of finite graphs: How can natural predicates and natural relations on a given natural base class $D$ be defined? If this succeeds the ...

**4**

votes

**0**answers

146 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

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

**4**

votes

**0**answers

94 views

### Full-rank factorization of the graph Laplacian

Is there a combinatorially meaningful full-rank factorization of the Laplacian matrix of a graph?
The usual factorization $L=BB^{T}$, where $B$ is an oriented incidence matrix, is full-rank if and ...

**4**

votes

**0**answers

35 views

### What is the probability of interpolating the Tutte polynomial of a planar graph from the values at the two hyperbolas?

The Tutte polynomial
is a bivariate polynomial with positive integer coefficient which is a graph
invariant and can be defined recursively.
Evaluating it is $\#P$-complete even when restricted to ...

**4**

votes

**0**answers

141 views

### Does the concept of connective constant make sense for any tiling of the plane?

First let me define what is the "connective constant" of a two dimensional lattice.
Let $c_{n}$ denote the number of $n$ step self-avoiding walks starting from a fixed origin point in the lattice. ...

**4**

votes

**0**answers

140 views

### Genus of the graph $K_{m,2,2,2}$

What is the genus of this complete $4-$partite graph, $K_{m,2,2,2}$, where $m \in \mathbb{N}$?
Thanks in advance.

**4**

votes

**0**answers

221 views

### Unique Domino Tiling

Question: how does one enumerate all star-convex $2n$-vertex sublattices of the plane that have the unique domino-tiling property?
Definitions:
A subset S of the xy-plane is star-convex if there is ...

**4**

votes

**0**answers

495 views

### Does this graph property have a name?

I'm interested in a family of properties of connected simple graphs that comes up in percolation theory.
Let $G$ be a simple connected graph. Now consider the set of subgraphs of $G$ that I will call ...

**4**

votes

**0**answers

413 views

### Questions about dessin d'enfants, trees and their Shabat polynomials

This will be a series of questions, a few of which have been troubling me for quite a while now. Before I jump right in, let me first introduce a few notions which I will assume.
(Note: All of these ...

**4**

votes

**0**answers

160 views

### Rough structure of the double coset space/Graph bijections up to automorphisms

I am dealing with bijective maps $\pi:\Gamma_1\to \Gamma_2$ between two graphs with the same number of vertices $N=O(10)$.
The graphs have a significant automorphism group (these are disconnected ...

**4**

votes

**0**answers

93 views

### Metrized categories

Motivation: Let $\Gamma = (V,E)$ be a directed graph. To each edge $e \in E$, choose a value $\kappa^e \in \mathbb R$, representing the cost of transporting one unit of "stuff" through the edge. Let ...

**4**

votes

**0**answers

153 views

### Graph distance of close points within the minimum spanning tree

My question is the following: Given $N$ uniform IID points $X=(X_1,...,X_N)$ on the unit cube of $\mathbb{R}^d$, take $X_1$ and another point, say $X_{(1)}$, "close" to $X_1$ (i.e. connected to $X_1$ ...

**4**

votes

**0**answers

119 views

### Graph drawing maximizing the volume of the convex hull

Given a graph $G=(V,E)$ and a length function $\ell:E\to\mathbb{R}_+$.
An embedding of the graph into the $d$-dimensional Euclidean space is a map $f:V\to\mathbb{R}^d$ such that ...

**4**

votes

**0**answers

211 views

### origin of the notion of “network” in graph theory

In current graph theory, a "network" is a precisely defined object: It is a directed graph associated with a function, the "capacity", which is defined on the edge set and has certain specific ...

**4**

votes

**0**answers

298 views

### Tensor product of quivers

As a special case of a general construction I have constructed "accidentally" a tensor product of quivers aka directed multigraphs (aka directed graphs for category theorists). Probably this is ...

**4**

votes

**0**answers

408 views

### System of Equations Upper Bound

I asked a related question on math.stackexchange here but would now like to obtain a better bound. This question comes from a graph theory problem. I'll restate the new question here:
For ...

**4**

votes

**0**answers

219 views

### Expected number of components with multiple cycles in a subgraph of a square lattice

Short version
Is there an understanding of the emergence and subsequent disappearance of components with zero, one, or more cycles in a random subgraph of a square or cubic lattice, as the ...

**4**

votes

**0**answers

146 views

### Bounds on numbers of matchings of given sizes in bipartite graphs

I am interested in the following question:
For which sets ${m_1,\ldots m_k}$ of positive integers do there exist bipartite graphs having exactly $m_i$ matchings of size $i$ for each $1\leq i \leq k$, ...

**4**

votes

**0**answers

411 views

### Smallest matrix covered by many random n by n matrices

We say that a matrix $M$ can be covered by a (smaller) matrix $N$ if every entry in $M$ is contained in some submatrix of $M$ that exactly equals to $N$, up to reordering the rows and columns of $N$. ...

**4**

votes

**0**answers

356 views

### SWAT vs Rioters (cops vs robbers variant)

I thought of this while at the Combinatorial Potlatch at Seattle University, where Peter Winkler gave an excellent talk on Cops vs Drunken Robbers. I'll just open it up to the floor. The problem ...

**4**

votes

**0**answers

338 views

### A binary bipartite graph - reference request

Consider the bipartite graph whose partite sets are two disjoint copies of $\{0,1\}^n$, with an edge joining $u$ and $v$ if and only if there is no position in which both $u$ and $v$ have $1$; that ...

**4**

votes

**0**answers

307 views

### An extremal problem for graphs having every edge contained in a 4-clique

This is a follow-up to Graphs with many triangles but few complete graphs on 4 vertices
I'm looking for an upper bound for the difference between the number of edges and the number of 4-cliques in a ...

**4**

votes

**0**answers

204 views

### Applying the amplification trick + probabilistic method on connected graphs

First of all, I apologise if my question is not very specific. I am not really looking for a concrete answer but rather some hints and pointers what could be used/applied in this situation. A concrete ...

**4**

votes

**0**answers

392 views

### Monotonic properties of harmonic functions on graphs

I have a question concerning monotonic properties of "generalized harmonic functions" on graphs. I am a physicist and I didn't take any separate courses in neither graph theory nor discrete harmonic ...

**4**

votes

**0**answers

491 views

### edge disjoint covers of graphs by paths

Let $G=(V,E)$ be a graph where every "internal" vertex has degree 4, and every "external" vertex has degree $\le 3$. What can be said about this graph if it can be covered by a collection of ...

**4**

votes

**0**answers

397 views

### Generating random polygons from a given triangulation of points

Given a triangulation $T$ of a planar set point $S$, we would like to randomly generate a polygon (hamiltonian cycle) $P$.
However, it has been proved that Hamiltonian Circuit Problem on maximal ...

**4**

votes

**0**answers

166 views

### Complex Laplacians in spectral decompostions of graphs

The Laplacian of a graph is a useful tool in many kinds of graph decomposition problems. Since inspection of the eigenvector corresponding to the second smallest eigenvalue (the Fiedler vector) yields ...

**4**

votes

**0**answers

110 views

### Limit Distribution of Topological Form of Polyhedra with Large Number of Edges

Consider the set of all topologically inequivalent polyhedral graphs with $k$ edges, the number of which is given by Sloan sequence A002840 (1,0,1,2,2,4,12,22,58,158,448)).
Now define a topological ...

**3**

votes

**0**answers

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

**3**

votes

**0**answers

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

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

**3**

votes

**0**answers

60 views

### Different definitions of linkless graphs

Robertson, Seymour and Thomas defined linkless embeddings of graphs as follows:
An embedding of $G$ is linkless if every pair of disjoint circuits of $G$ have zero linking number (see here). However ...