**3**

votes

**0**answers

42 views

### Balancing out edge multiplicites in a graph

Let $G$ be a multigraph with maximum edge multiplicity $t$ and minimum edge multiplicity $1$ (so that there is at least one 'ordinary' edge).
Is there some simple graph $H$ such that the $t$-fold ...

**3**

votes

**0**answers

97 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

**0**answers

186 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

**0**answers

168 views

### Partitioning a cubic graph into two induced cycles of equal order

I am aware that deciding the existence of a partition of the vertices of a connected graph $G(V, E)$ into two induced cycles is $NP$-complete(Theorem 2). Induced cycle is a cycle without any chord ...

**3**

votes

**0**answers

177 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

**0**answers

78 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

**0**answers

143 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

**0**answers

167 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

**0**answers

262 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

**0**answers

145 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

**0**answers

85 views

### Usefulness of polynomial ideals for graphs

Given a graph $G=(V,E)$ on $n$ vertices, one can associate to it the polynomial $f \in k[x_1,\dots,x_n]$ given by $f = \prod_{\{i,j\}\in E}(x_i - x_j)$. Then one can map various graph properties into ...

**3**

votes

**0**answers

146 views

### Maximize weighted vertex sequence subject to neighbour inclusion

Let $G=(V,E)$ be a simple undirected graph on $n$ nodes, with node weights $W = [w_1,w_2,\dots,w_n] \in \mathbb{R}^n$. Define the weight for a sequence of nodes $v_1,v_2,\dots,v_k$ by the average ...

**3**

votes

**0**answers

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

**3**

votes

**0**answers

59 views

### Is the $d$-dimensional Arrangement of Trees still $NP$-hard?

The $d$-dimensional Arrangement Problem for general graphs is known to be $NP$-hard since the special case $d=1$ (OLA) already is (Garey et al, [1976]). For Trees however, the one dimensional case can ...

**3**

votes

**0**answers

254 views

### How many trees can be constructed from k vertices using an LCA operator?

Consider the class of rooted trees and suppose I have at my disposal a lowest common ancestor (LCA) operator given by
$$
\textrm{lca}(u,v) = \text{the lowest common ancestor of $u$ and $v$}
$$
for all ...

**3**

votes

**0**answers

70 views

### Is there precedent in the literature for a variant of a random geometric graph where vertices are the centroids of discs placed by random sequential adsorption (RSA)?

Imagine I form a random graph by simulating random sequential adsorption (RSA) of discs (each with the same radius $r$) on $[0,1]^2$ until I cover the plane at a density $\leq U$, where $U \leq ...

**3**

votes

**0**answers

166 views

### Is there a flow criterion for a graph being planar?

Given the set od propagators (say momenta flows) on a Feynman diagram (flow network), I would like to decide whether this diagram is planar or not.
I know that non-planar diagrams manifest different ...

**3**

votes

**0**answers

410 views

### Minimum weight bipartite graph clique covering

I was wondering if anyone here could give me any pointers as to how to solve the following problem.
Let $B=(L,R,E)$ be a bipartite graph, and $\forall u\in L\cup R$, let $c_u$ be a cost associated to ...

**3**

votes

**0**answers

160 views

### Generalised de Bruijn Graph

I have encountered sets of the following type, consisting of words over a finite aphabet $A$.
If $S$ is such a set, then
$S$ is finite,
No word in $S$ is part of another element of $S$, and
every ...

**3**

votes

**0**answers

128 views

### The mean number of vertices in small connected components of random geometric graphs

I place $N$ points on a circular plane of radius $R$, and draw edges to connect points that are less than or equal to some distance $D$ to form a set of graphs or cliques $G_i$. As a function of $N$, ...

**3**

votes

**0**answers

119 views

### On the faces of the multicommodity flow polytope

Consider the multicommodity flow problem on an undirected graph with k source-destination pairs and specified capacity constraints on the edges. The set of concurrently achievable flows ...

**3**

votes

**0**answers

185 views

### Bounds on number of small minimal cut-sets in graph?

David Karger developed an algorithm for estimating graph reliability; a key lemma in this algorithm is that if a graph has minimal cut-set size $c$, then the number of cut-sets of size
$\alpha c$ is ...

**3**

votes

**0**answers

185 views

### Minimum sum of distances of G for spanning tree of G

Let $G=(V,E)$ be a undirected simple graph, and $\Omega(G)$ denote the set of spanning trees of G. Does the next funcion
$$l(G) = \min_{T \in \Omega(G)}\quad \sum_{uv \in E} \mbox{dist}_T(u,v)$$
have ...

**3**

votes

**0**answers

118 views

### Polynomials in graphs

I have part of a physical simulation which I've realised can be modelled using a directed graph where each node is a polynomial. I then calculate this graph by functional composition and summing to ...

**3**

votes

**0**answers

239 views

### Minimal-edge graph with diameter 2 and bounded max degree

Consider all connected simple graphs with diameter $d = 2$ and maximal vertex degree $\Delta$. In my particular practical case $\Delta = 4$, but general problem is much more interesting — probably ...

**3**

votes

**0**answers

237 views

### Domination number of hamming graphs

The problem of finding the domination number of Hamming graph $H(3, 2n)$ ($n$ is an integer) was given as a homework for my discrete math class. I didn't manage to solve the question. But later the ...

**3**

votes

**0**answers

301 views

### Computing Quantum Dimensions

Hi,
in "Jaeger’s Higman-Sims state model and the B2 spider" by Greg Kuperberg
(arxiv:math9601221v1, 1996) there are some quantum dimensions listed in the
"Discussion" part. Evidently quantum groups ...

**3**

votes

**0**answers

205 views

### For Ising models on finite graphs, is the gradient of Z (w/r/t coupling and field) easier to compute than Z?

Suppose we have a graph $G$ with $n$ vertices, edgeset $E$, $\mathcal{X}=\{1,-1\}^n$. The partition function of the spin-1/2 Ising model on $G$ is
$$Z(J,h)=\sum_{x\in \mathcal{X}} \exp\left(J ...

**3**

votes

**0**answers

126 views

### Dimension of convex arrangements for hypergraphs

Suppose you have a hypergraph H on n vertices. Let d be the smallest integer such that we can find an arrangement A of convex subsets in Rd so that H represent the intersections of sets in A.
Has ...

**3**

votes

**0**answers

403 views

### Graph recognition software

ISGCI lists a lot of graph classes, many of which are recognizable in polynomial time. Is anyone here aware of actual implementations of these algorithms?

**3**

votes

**0**answers

404 views

### cell complexes and higher graph theory

Suppose that, on an intuitive basis, one defines a "2-graph" $(V,E,F,\partial)$ as a collection of vertices, oriented edges and oriented faces, all of which should be considered as abstract objects ...

**2**

votes

**0**answers

56 views

### Even cycle constrained edge coloring

Is minimum colors needed to assign colors to edges of complete graph $K_n$ so that every $2t$ simple cycle where $t\in\Big\{1,\dots,2\Big\lfloor\frac{n}2\Big\rfloor\Big\}$ contains atleast $t+1$ ...

**2**

votes

**0**answers

45 views

### Maximum cardinality general factor of a graph

Given a graph $G=(V,E)$ and a set of integers $B(v)$ associated to each vertex, a general factor of $G$ is a set of edges $F\subseteq E$ such that the degree of each vertex $v\in V$ in the graph $(V, ...

**2**

votes

**0**answers

35 views

### Is this infinite family of non-trivial snarks resulting from the first Celmins-Swart?

Non-trivial snark is cubic graph with chromatic index $4$, girth
at least $5$ and doesn't to contain three edges whose deletion results in a disconnected graph, each of whose components is nontrivial.
...

**2**

votes

**0**answers

122 views

### Polynomial-time algorithm solving approximately a generalization of the travelling salesman problem

Take a graph $G$ and a number of sets of nodes of $G$. The problem is to find the shortest path passing through at least one node in each node set. If each node set consists of only one node, the ...

**2**

votes

**0**answers

49 views

### Decomposing a weakly chordal graph into disjoint union of co-chordal graphs

A graph G is said to be co-chordal if it is $\bar C_n$-free for any $n \ge 4$. It is weakly chordal if it is $C_n$ and $\bar C_n$ free for all $n\ge 5$. Assume that the induced matching number of $G$ ...

**2**

votes

**0**answers

63 views

### Edge-disjoint path-systems in infinite digraphs

Let $ D=(V,A) $ be a directed graph without backward-infinite paths and let $ \{ s_i \}_{i<\lambda},U \subset V $ where $
\lambda $ is some cardinal. Assume that for all $ u\in U $ there is a ...

**2**

votes

**0**answers

44 views

### Mappings between adaptive networks and Markov processes

Are there any known mappings between adaptive networks models (i.e. graph model representations of networks where the internal vertex dynamics and connectivity topology can change subject to specific ...

**2**

votes

**0**answers

22 views

### Is it true that centrality measures in SNA are indicative for most important vertices only?

I read about the limitations of centrality measures on Wikipedia. It says that centrality measures are good only for identifying top most important nodes in a social network. Their relative values can ...

**2**

votes

**0**answers

52 views

### Is the size of maximum matching in vertex transitive 3-uniform hyper-graph on $n$ vertices always $\Omega(n)$?

What is the best known lower bound on the size of the maximum matching in a vertex transitive $3$-uniform hyper-graph?

**2**

votes

**0**answers

111 views

### About the small set expansion conjecture

Given a graph $G=(V,E)$ and a $\delta > 0$ one wants to calculate $h(G,\delta)=min_{\vert S\vert \leq \delta \vert V \vert } \phi(S)$. ($\phi(S) = \frac{ E(S,\bar{S}) }{d min \{\vert S \vert , n - ...

**2**

votes

**0**answers

98 views

### the choosing of an independent set in a specific $k$-partite graph

Let $k\geq2$ be an integer, a graph $G=(V,E)$ is called $k$-partite if $V$ admits a partition into $k$ classes such that every edge of $G$ has its ends in different classes: vertices in the same class ...

**2**

votes

**0**answers

113 views

### Discrete p-Laplacian

One of the definitions of the discrete (weighted) $p$-Laplacian is the following:
$$\Delta_{p,w}u(x):=\sum_y |u(y)-u(x)|^{p-2}(u(y)-u(x))w(x,y).$$
Consider the one dimensional case. Then the free ...

**2**

votes

**0**answers

96 views

### Isomorphic subcategories of directed graphs and presets

For the purposes of this post, a digraph (directed graph) has neither loops nor multiple parallel edges, and a preset is an ordered pair consisting of a set $S$ and a preorder (viz., a reflexive and ...

**2**

votes

**0**answers

48 views

### Counting labelled graphs according to sets of size 3

In this question we are counting labelled simple graphs. No concept of isomorphism is involved.
Let $G(n,e,t)$ be the number of labelled simple graphs with $n$ vertices, $e$ edges, and $t$ sets of ...

**2**

votes

**0**answers

50 views

### finding dominating cycles in $2K_2$-free graphs

A cycle $C$ in a connected graph $G$ is called dominating if its complement $V(G)-V(C)$ is an independent set. H.J. Veldman proved in 1983 (Disc. Math. v.43, 281-96) a general result that in ...

**2**

votes

**0**answers

70 views

### Total number of spanning trees of a set of graphs

Given an undirected graph G with $n$ nodes, we can compute its number of spanning trees in polynomial time using Kirchhoff's matrix-tree theorem. Now consider a more complicated setting, in which each ...

**2**

votes

**0**answers

64 views

### relationship of max-sat and min-cut in theory and practice

I have been using MAX-SAT solver to obtain the exact ground state of ising spin glass model:
For 1D periodic model, for systems with 50 binary variables and interaction range of 15th nearest ...

**2**

votes

**0**answers

77 views

### Are there two-sided $\varepsilon$-expanders with independent sets of size $(1-\varepsilon)n$?

Terry Tao's notes on expander graphs has the following exercise:
Exercise 13 Let $G$ be a $k$-regular graph on $n$ vertices that is a two-sided $\epsilon$-expander for some $n > k \geq 1$ and ...

**2**

votes

**0**answers

54 views

### Fixing (non)-independency of a the subfamilies of finitely many events.

I'm would be interesting in any construction of a probability space with n events (n is given), where for every subset of these events, it is also given whether or not, the family is mutually ...