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

5
votes
0answers
106 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
162 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
450 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 ...
5
votes
0answers
134 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
92 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
134 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
0answers
225 views

How does the distribution of Erdős number evolve over time ? How to build a model to fit the real data ?

Let $E(n,t)$ be the number of mathematicians with finite positive Erdős number $n$ at time $t$. As old mathematicians leave, and new mathematicians come, how does $E(n,t)$ change over time ? We can ...
5
votes
0answers
349 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 ...
5
votes
0answers
269 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
228 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
751 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 ...
5
votes
0answers
394 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
581 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
411 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
137 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
134 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
144 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
136 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 ...
4
votes
0answers
152 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
92 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
140 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
194 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
286 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
117 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 ...
4
votes
0answers
398 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
192 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
211 views

Graphs which are “distance-regular” with respect to a vertex (but not distance-regular)

A distance-regular graph (DRG) is, in essence, a graph $\Gamma$ of diameter $d$ for which there are integers $c_i, a_i, b_i, (0 \le i \le d)$ such that for all vertices $x$ of $\Gamma$ and for all ...
4
votes
0answers
142 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
406 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
337 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
0answers
290 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
200 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
382 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
452 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
387 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
161 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
107 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
112 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
47 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$. ...
3
votes
0answers
63 views

When is an induced subgraph of a Johnson graph hamilton-connected?

The Johnson graph $J(n,k)$ has vertices which are the $k$-subsets of $\{1, 2, \dots, n\}$ where two vertices are adjacent iff their intersection has size $k-1$. A graph is hamilton-connected if every ...
3
votes
0answers
155 views

vertex transitive and Cayley graphs

(all the graphs alluded to below are finite). Suppose I gave you a graph, and asked you whether it was vertex-transitive. How hard is that algorithmically? The second question is: suppose I gave you ...
3
votes
0answers
146 views

Hitting edges in graphs at random and let them die with honor

Let $G=(V,E)$ be a finite simple 2-connected graph. Let $B\subseteq E$ be a set of bad edges of size $k:=|B|$. For each edge $e\in E$ we toss a fair coin ($p=1/2$) and if the outcome is head, we hit ...
3
votes
0answers
70 views

What is this expander-mixing-type graph property?

Fix $C>0$. I am interested in graphs with the following mixing property: $$\Big|E(S,T)-\frac{1}{2}|S||T|\Big|\leq C\sqrt{|S||T|\max\{|S|,|T|\}}$$ for every disjoint $S,T\subseteq V$. Note that ...
3
votes
0answers
68 views

Size of b-matching constructed from b maximal matchings

The Question: Let $G$ be a (simple) graph and let $b\in\mathbb{N}$. Suppose that we have $b$ disjoint edge-subsets $M_1,\ldots , M_b$ satisfying the following condition: The set $M_1$ is a maximal ...
3
votes
0answers
107 views

Concentration inequality for function of independent Bernoulli r.v.'s (related to random graph)

Consider a random undirected graph on a set of $n$ nodes, say $\{1,2,\ldots,n\}$, such that the probability of edge between nodes $i$ and $j$ is $p_{ij}$ (we may assume $p_{ij}=o(1)$ for all $i,j$, ...
3
votes
0answers
155 views

Bits required to encode difference between number of subgraphs with odd number of edges and number of subgraphs with even number of edges

Let $H = ( V, E )$ be a $k$-uniform connected hypergraph, with $n = |V|$ vertices and $m = |E|$ hyperedges. Let $O_w$ be the number of edge induced subgraphs of $H$ having $w$ vertices and an odd ...
3
votes
0answers
366 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 ...
3
votes
0answers
207 views

A problem on graph theory and complex numbers!

Let ${\mathcal G} = ({\mathcal V},{\mathcal E})$ be a simple connected undirected graph with $n$ vertices. Also let $z_1, \ldots, z_n \in {\mathbb C}$ be complex numbers such that $$ ||z_1||=\ldots = ...
3
votes
0answers
119 views

Equivalent paths in graphs

Let $G$ be a finite, planar graph. In this question I consider a path in $G$ to be a finite sequence of vertices $v_1,\dots,v_n$ of $G$, where $v_i$ is adjacent to $v_{i-1}$ for $i=2,\dots,n$. A ...
3
votes
0answers
158 views

Beating Kadane's Algorithm

I am seeking some reference on already existing work for the following problem. Given an $n$-dimensional square matrix $A=DP$ where $D$ is a diagonal and $P$ is a permutation matrix (think of Gaussian ...