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

6
votes
0answers
338 views

What is this subclass of $k$-colorable graphs called?

The following property emerged naturally when I was playing with certain generalizations of Kneser graphs. Let $k>0$ be a natural number. Consider a property $P_k$ of graphs defined as follows. ...
6
votes
0answers
933 views

What is the best lower bound for the domination number in regular graphs of girth 5?

The following theorem is a classical result (see [Alon and Spencer, The probabilistic method, 2nd ed., Theorem 1.2.2]): Theorem: Let $G$ be a graph on $n$ vertices with minimum degree $d$. Then ...
6
votes
0answers
625 views

inverse eigenvalue problem on graph laplacian

I am trying to construct a graph Laplacian matrix from a set of eigenvalue. I've read several papers about inverse eigenvalue problems but to be honest I didn't understand clearly. Could somebody ...
6
votes
0answers
718 views

Simplicial Representations of (Hyper)Graph Complexes

For graph complexes, which are families of graph [on a fixed number of vertices n] closed under the deletion of edges, there is a natural simplicial complex capturing that information. Specifically, ...
5
votes
0answers
59 views

When is the tensor product of two graphs planar?

Given two graphs $G=(V_1,E_1)$ and $H=(V_2,E_2)$, the tensor product of $G$ and $H$ is the graph $G \times H = (V,E)$, where $V=V_1 \times V_2$ is the Cartesian product of the $V_i$ and $ (u,v) \ E \ ...
5
votes
0answers
193 views

When does a “stable” assignment of buyers into goods exist?

Consider a setting of $n$ buyers and $m$ goods. We have a value matrix $V\in[0,1]^{n\times m}$ specifying how much each buyer values each good (everything is open information here and there is no ...
5
votes
0answers
99 views

What's the variance in the Six Degrees model?

Recall the six degrees of Kevin Bacon game. You can even play the game at The Oracle of Bacon, and their search works via Breadth First Search. I interpret the punchline as saying that if I start ...
5
votes
0answers
152 views

Sets of spreads in graphs

Let $G$ be a graph. A $k$-spread is a set of cliques of order $k$ which partition the vertex set (so $k|n$, where $n$ is the number of vertices). A partial $k$-resolution of $G$ is a set of pairwise ...
5
votes
0answers
76 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
0answers
162 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
0answers
88 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
0answers
156 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
0answers
87 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
0answers
117 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
0answers
167 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
0answers
164 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
0answers
152 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
0answers
98 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
0answers
135 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
0answers
281 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
0answers
235 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
0answers
352 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 ...
5
votes
0answers
399 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
0answers
589 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
0answers
431 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
0answers
116 views

minimal polynomial for a graph

I wonder if there is any result relating the degree $d$ of the minimal polynomial of a directed finite graph to any of its topological features - such as its diameter, or any other similar 'natural' ...
4
votes
0answers
186 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 ...
4
votes
0answers
85 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
80 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
0answers
38 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
154 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
144 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
244 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
511 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
104 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
442 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
167 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
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
0answers
165 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
120 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
220 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
313 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
168 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
412 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
237 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
148 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
412 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
363 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
313 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
208 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 ...