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
600 views

Is Logical Min-Cut Problem, NP-Complete?

Logical Min Cut (LMC) Problem: Suppose that G = (V, E) is an unweighted digraph, s,t are two vertices of V, and t is reachable from s. LMC Problem states that how we can make t unreachable from s by ...
6
votes
0answers
342 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
997 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
648 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
742 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
168 views

Unique Nash equilibrium games

Multicast network design game is a special case of a general network design game (http://www.cs.cornell.edu/home/kleinber/focs04-game.pdf) in which there is a target vertex $t$ and $n$ rational ...
5
votes
0answers
77 views

Graphs with no homomorphism and no minor relation

What is an example of two simple, undirected graphs $G,H$ such that there are no graph homomorphisms between $G, H$, and $H$ is not a minor of $G$, and $G$ is not a minor of $H$ ? Definition of ...
5
votes
0answers
67 views

Determinantal formulae for Tutte polynomial

Let $G$ be a connected undirected graph. Then the number $ST(G)$ of spanning trees in $G$ equals the following specific value of the Tutte polynomial of $G$: $ST(G)=T_G(1,1)$. On the other hand, ...
5
votes
0answers
46 views

Perfect matchings of a regular, uniform, partite hypergraph

This is in relation to the question here. What, if any, are the known conditions for the existence of a perfect matching for a $r$-regular, $r$-uniform, $r$-partite hypergraph. I specifically ...
5
votes
0answers
62 views

Approximating a max-cut's intersection with other cuts

(This is a cross-post from the Theoretical Computer Science Stack Exchange.) For the purposes of this question, a cut in a graph $G$ is the edge-set $\delta (S)\subseteq E(G)$ between some vertex-set ...
5
votes
0answers
103 views

A digraph related to permutations

A finite sequence of distinct real numbers of length $n$ determines a linear order of $\{1,\ldots,n\}$, by mapping position to rank; call this the permutation of the sequence. Consider the following ...
5
votes
0answers
205 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
105 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
163 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
114 views

Cores of infinite graphs

Let $\kappa$ be a cardinal and let $\textrm{Grph}(\kappa)$ be the set of graphs $G = (V,E)$ such that $V \subseteq \kappa$ and $E \subseteq \mathcal{P}_2(V) := \{\{a,b\} \subseteq V: a\neq b\}$. We ...
5
votes
0answers
93 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
93 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 ...
5
votes
0answers
179 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
95 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
171 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
90 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
123 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
169 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
201 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
161 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
99 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
147 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
289 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
240 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
362 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
592 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
442 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
78 views

Does squaring a directed random graph more than double its out-degree?

As far as I know, it is an unsolved question whether or not this is true: If $G$ is a directed an oriented graph, $G^2$ always has some node whose outdegree is at least double that of its ...
4
votes
0answers
45 views

Existence of certain graph gadget related to coloring odd hole free graph

Wondering about the existence of graph gadget related to coloring (or 3-coloring) odd hole free graphs. Let $G$ be simple $k$-chromatic connected graph with two vertices $u,v$. Is it possible $G$ to ...
4
votes
0answers
87 views

Prove or disprove a claim about covering a polytope by convex polytopes in a certain way

Here is the claim: Given a polytope $K$ in a unit ball in $\mathbb{R}^d$, there exists a universal constant $C(d)>0$ depending only on $d$ and a countable collection of convex polytopes ...
4
votes
0answers
39 views

Digraph weak connectivity in $O(V)$ space and $O(V+E)$ time

A digraph is called weakly connected if its underlying undirected graph is connected. You are given a digraph $G$ with $V$ vertices and $E$ edges as a read-only data structure consisting of lists of ...
4
votes
0answers
93 views

Counting vertex-permutations of a finite tree which rip all edges

Given a finite tree $T$ with $n$ vertices labelled $1,\dots,n$, we say that a permutation $\sigma$ of $1,\dots,n$ rips all edges if $\{\sigma(i),\sigma(j)\}$ is never an edge for every edge $\{i,j\}$ ...
4
votes
0answers
130 views

Connection between connectivity and cohesion of a graph

Tutte [1] proved that, for every $3$-connected graph $G$ and vertices $u$ and $v$, there exists a nonseparating $uv$-path. A graph $G$ is $t$-cohesive if $G$ is connected, has at least two vertices, ...
4
votes
0answers
143 views

What is known about the complexity of this covering problem?

Let $G=(V,E)$ be a graph. A vertex set $X\subseteq V$ is called critical if $X\neq\emptyset$ and no vertex in $V\setminus X$ is adjacent to exactly one vertex in $X$. The problem is to find a vertex ...
4
votes
0answers
124 views

Hypercube edge-coloring problem

Question: Is there a pairing (a fixed point free involution) of the vertices of the $n$-dimensional cube graph, and a $2$-coloring of its edges such that the number of color changes needed to get from ...
4
votes
0answers
60 views

Linear intersection number and coloring (not chromatic) number

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 ...
4
votes
0answers
33 views

Isomorphic Hadwiger graphs of connected infinite graphs

Let $G$ be a graph, then we define its Hadwiger graph $\textrm{Hadw}(G)$ in the following way: $V(\textrm{Hadw}(G)) = \{S\subseteq (V(G): S\neq \emptyset\textrm{ and } S \textrm{ is connected}\}$; ...
4
votes
0answers
125 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
194 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
88 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
45 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.