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

4
votes
0answers
89 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 ...
4
votes
0answers
133 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 ...
4
votes
0answers
46 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
0answers
155 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
0answers
145 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
0answers
266 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
0answers
517 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
0answers
83 views

Upper bound on size of obstruction set for wye-delta-wye reducible graphs

A graph is $Y \Delta Y$-reducible if it can be reduced to an empty graph by the following operations: $Y \leftrightarrow\Delta$ transforms; Replacing multiple edges with single edges (parallel ...
4
votes
0answers
111 views

What are the best bounds to date on the maximum girth of a cubic graph?

The girth of a graph is the length of its smallest cycle. Studying the maximum possible girth for a $k$-regular graph on $n$ vertices is a very well-studied problem. In the 1988 paper "Ramanujan ...
4
votes
0answers
489 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
0answers
173 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
0answers
98 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
0answers
179 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
0answers
128 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
0answers
233 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
0answers
558 views

determinant of fibonacci-sum graphs

We have a simple graph with vertices $\{v_1, v_2, ... v_n\}$. The adjacency matrix of this graph is $A= (a_{ij})$ so that $a_{ij}=1$ if $i+j$ belongs to the Fibonacci sequence; $a_{ij}=0$ ...
4
votes
0answers
334 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
0answers
171 views

Shannon capacity of all graphs of order 6

In Shannon's paper, "The Zero Error Capacity of a Noisy Channel", he says that the Shannon capacity of all graphs of order 6 are determined, except for four exceptions. That is, for all but the four ...
4
votes
0answers
418 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
0answers
268 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
0answers
161 views

Best lower bound for proof complexity of graph asymmetry

Graph automorphism problem ( GA) of determining whether a graph has a nontrivial automorphism is a good candidate for a problem in $NP$-intermediate. I'm looking for references that study the ...
4
votes
0answers
151 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
0answers
421 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
0answers
371 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
0answers
321 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
0answers
210 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
0answers
404 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
0answers
521 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
0answers
408 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
0answers
172 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
0answers
322 views

Combinatorics of signed oriented graphs/skew-symmetric matrices

Consider a "complete" signed graph on $n$ vertices indexed by $1,2,\dots,n$, that is, a graph in which any two distinct vertices $i$ and $j$ are connected by an oriented edge. For each pair of ...
4
votes
0answers
111 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
0answers
81 views

Does this notion of “$\mathcal{F}$-digraph” appear in the literature?

By a digraph, I mean a quiver with no multiple edges. So in particular: Loops are okay. An infinite set of vertexes is okay. Furthermore, I will tend to identify each digraph with its underlying ...
3
votes
0answers
61 views

Relationship of Weisfeiler-Lehman algorithm to weak isomorphism of coherent algebras

A coherent algebra is a matrix algebra (over $\mathbb{C}$) closed under conjugate transpose and Schur (entrywise) product, and that contains the identity matrix $I$ and all ones matrix $J$. Given ...
3
votes
0answers
55 views

Linear intersection number of a product of graphs

A linear hypergraph is a pair $\pi=(X, L)$ where $X\neq \emptyset$ is a set and $L\subseteq {\cal P}(X)$ has the following properties: for $e\in L$ we have $|e|\geq 2$; if $e_1\neq e_2 \in L$ then ...
3
votes
0answers
55 views

Strongly minimal covering subsets of $\text{Ind}(G)$

Let $G=(V,E)$ be any undirected, simple graph. Let $\text{Ind}(G)$ be the set of independent subsets of $V(G)$. We say that $K\subseteq \text{Ind}(G)$ is a cover (by independent subsets) if $\bigcup K ...
3
votes
0answers
50 views

The Class of Strong Resolving Graphs of Hamiltonian Outerplanar Graphs

I'll start with a couple important definitions. I'm not sure how well-known any of them are. Firstly, if $G$ is a graph, and $u, v \in V(G)$, say that $u$ is maximally distant from $v$, denoted $u\ ...
3
votes
0answers
28 views

Minimality of maximal expansions of a hypergraph cover

This is a follow-up question to Maximal expansions of strongly minimal covers of hypergraphs. Let $H = (V,E)$ be a hypergraph, that is $V$ is a set and $E \subseteq {\cal P}(V)$. We assume $\bigcup E ...
3
votes
0answers
159 views

Characterizing graphs with $k$ edge-disjoint minimum diameter spanning trees

Henneberg [1] and Laman [2] characterized graphs which have, after adding any edge, 2 edge-disjoint spanning trees. This was generalized to $k$ edge-disjoint spanning trees by Frank and Szegõ [3]. ...
3
votes
0answers
133 views

What mathematical models can analyze and optimize systems based on gossip?

I look for a mathematical model that can accommodate, analyze and suggest optimizations for a system that can be humanly described as people gossiping about stuff. System description: We have a ...
3
votes
0answers
193 views

The Bilu-Linial conjecture and Ramanujan graphs

The Bilu-Linial conjecture claims that every $d-$regular graph has a $2-$lift such that for the signing matrix has its eigenvalues between $[-2\sqrt{d-1},2\sqrt{d-1}]$ (the ``signing matrix" is the ...
3
votes
0answers
121 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
0answers
99 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 ...
3
votes
0answers
70 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 ...
3
votes
0answers
46 views

Algorithm to construct metric space endomorphism with controlled square

Given a finite metric space $(M,d)$ with parameters $K \geq 1$ and $\epsilon > 0$, I'd like to algorithmically check for the existence of a non-identity map $\phi:M \to M$ which happens to be ...
3
votes
0answers
96 views

Node covering in a random graph

Given $N$ nodes randomly placed in a $D\times D$ area, i.e., the position of each node is randomly chosen. Assume that both $N$ and $D$ are sufficiantly large. An agent can move in the area at ...
3
votes
0answers
64 views

Maximal $k$-chordal subgraph

Recall that a graph is called $k$-chordal if any cycle $C$ of length $> k$ contains a chord, i.e. an edge joining to non-consecutive vertices in $C$. Let $f(n, k)$ be the minimal number of edges ...
3
votes
0answers
86 views

Reconstructing a function from its variants that negate one argument

Call two functions $g(x_1,\ldots,x_n)$ and $h(x_1,\ldots,x_n)$ from complex numbers to complex numbers equivalent if they are the same up to the order of their arguments. Formally: there is a ...
3
votes
0answers
152 views

Must distinct tree eigenvalues be relatively far apart?

How close to each other can two distinct eigenvalues of a tree be, as a function of the number $n$ of nodes ? For example, the path $P_n$ exhibits a gap of order $\frac{2\pi^2}{n^2}$ asymptotically ...
3
votes
0answers
103 views

Independence Number of K4-free planar graphs

The independence ratio is defined as the size of the maximum independent set divided by $n$. By the 4-color theorem, every planar graph with $n$ vertices has independence ratio at least $1/4$. ...