**1**

vote

**0**answers

95 views

### Bipartite independence number

Consider a balanced bipartite graph $G=(U,V,E)$, i.e., a bipartite graph with $|U|=|V|$. An independent set $I$ of $G$ is balanced if $|I \cap U| = |I \cap V|$.
The bipartite independence number of ...

**1**

vote

**0**answers

102 views

### When does the induced directed graph of a directed multigraph preserve information?

Let G be a directed multigraph, and let H be the induced directed graph whose vertices are the edges of G, and whose edges are given by pairs of consecutive edges in G; i.e., there is an edge from v ...

**1**

vote

**0**answers

359 views

### What is a good algorithm to measure similarity between two dynamic graphs?

I am using graphs to represent structure present in a scene. The vertices represent the objects in the scene and the edges represent the relationship between two nodes(touching, overlapping, none). ...

**1**

vote

**0**answers

114 views

### What is the expected Cheeger constant of a random graph?

Recall that the Cheeger constant (AKA isoperimetric constant) of a graph $G$ is the infimum of $\frac{\partial S}{vol S}$ over all subsets $S$ of $G$ with volume no larger than $vol(G)/2$. I would ...

**1**

vote

**0**answers

69 views

### Terminology question: maximal non-branching directed paths

Is there any special word for a maximal non-branching directed path in a network or diforest?
To be 100% precise, by "maximal non-branching directed path" I mean a path $P=x_1,x_2,\ldots$ (maybe ...

**1**

vote

**0**answers

84 views

### Excluding linear size independent sets in graphs

What are some known criteria of excluding large independent sets (linear size) in k-regular graphs?
I know one criterion is that the smallest eigenvalue of the adjacency matrix shouldn't be too small ...

**1**

vote

**0**answers

56 views

### Details about Kelman's equivalent form of Barnette's conjecture

Barnette's conjecture states that every cubic planar bipartite 3-connected graph admits Hamiltonian cycles.
Kelman claims that this conjecture is equivalent to a stronger one, which imposes some ...

**1**

vote

**0**answers

63 views

### Effect of removing a Hamiltonian cycle on the Laplacian spectrum

Notation: $\lambda_{\max}(G)$ is the largest eigenvalue of the Laplacian matrix of the graph $G$ (aka the Laplacian index of $G$).
Now suppose $G$ is a Hamiltonian graph with Hamiltonian cycle $C$.
...

**1**

vote

**0**answers

147 views

### Self-modelling structures

Consider - for the sake of simplicity - only graphs as structures.
For undirected graphs $(V, E\subseteq \binom{V}{2})$ let
$E(v)$ be the set of edges $e\in E$ incident with $v$, i.e. $\lbrace e ...

**1**

vote

**0**answers

63 views

### Second eigenvalue of a weighted tree

Hello,
I am interested in upper bounding the second largest eigenvalue of the adjacency matrix of a graph $T$ with the following property:
1. $T$ contains self loops.
2. $T$ contains multiple edges ...

**1**

vote

**0**answers

115 views

### Recovering a partition from spectral properties of the graph Laplacian

Let $G$ be a weighted graph with vertices $V$. Let $W$ be its real-valued, non-negative, $|V|\times|V|$ adjacency/affinity matrix. Let $L = \mathrm{diag}(W\mathbf1)-W$ be the (unnormalized) graph ...

**1**

vote

**0**answers

105 views

### Optimization over Spectral Laplacian in cycles and trees

Is there any idea on how one can deal with an optimization problem of sum of k largest eigenvalues(min) of Laplacian matrix of a simple cycle or tree?
I would like to use semidefinite programming for ...

**1**

vote

**0**answers

55 views

### Can this application of the moment closure method to epidemics on networks be made rigorous?

Short version: Consider the SI model of infectious disease spread on a random graph $G$ with a given degree sequence. Let $j$ be a vertex and let $i$ and $k$ be two of its neighbors. If $G$ ...

**1**

vote

**0**answers

54 views

### shortest path in undirected graph in LogSpace

Given an undirected graph G (can be cyclic) with the promise that all its faces have 3 sides is it possible to find the minimum distace between a source and any other vertices in LogSpace or in ...

**1**

vote

**0**answers

69 views

### Number of edges in graph in terms of reliability

Consider a connected graph $G$ with min-cut $c$. Suppose the edges fail (are removed) independently with probability $p$. Then $U(p)$, the probability that $G$ becomes disconnected, is at least $p^c$. ...

**1**

vote

**0**answers

91 views

### Schönhage's SMM with only one instruction

It is possible to implement $\lambda$-calculus in Schönhage's storage modification machine using an infinite set of nodes and one single program consisted exclusively of (about hundred) instructions ...

**1**

vote

**0**answers

84 views

### Set of upper bounds is finite for any finite subset

Is there a term to describe a preordered set $P$ in which any finite subset $S \subset P$ has at most finitely many minimal upper bounds? The preordered sets I'm studying generally aren't ...

**1**

vote

**0**answers

102 views

### Turing-complete primitive interaction systems

Let us call primitive an interaction system with the signature
$\Sigma = \{(\rho, 0), (\xi, n)\}, \quad n \geq 2;$
and the only rule being of the form
$\rho \bowtie \xi[\rho, \xi(a_1, \dots , a_n), ...

**1**

vote

**0**answers

116 views

### regular hyper graph construction

Is there any algorithm to generate 3-uniform k-regular hypergraph with n vertices?? Any help is appreciated. Thanks.

**1**

vote

**0**answers

53 views

### Are morphisms of intersection graphs of circle packings harmonic?

Let $P$ and $Q$ be circle packings on compact Riemann surfaces (along with some Riemannian metrics) $X$ and $Y$. Let $f\colon X\to Y$ be a conformal map taking each circle in $P$ to a circle in $Q$. ...

**1**

vote

**0**answers

118 views

### Non-trivial lower bound on the number of “Graph Diagonals”

The definition of Graph Diagonals, that are the subject of this question, is based on the notions of crossing edges and on connected graphs:
Two edges $AC$ and $BD$ of a complete, symmetric and ...

**1**

vote

**0**answers

209 views

### Applications of line graphs

I am trying to collect a few examples of applications of line graphs in sciences other than mathematics. To be more precise: I am thinking of models where there is a clear conceptual added value in ...

**1**

vote

**0**answers

60 views

### triangles in a graph with specified clique number

Turan's theorem tells us that if m is the number of edges in a graph with n vertices and clique number r, then 2m <= (r - 1)n^2/r.
If t denotes the number of triangles, is there a similar ...

**1**

vote

**0**answers

117 views

### Geodesics in polyhedral graphs

Let $e = \lbrace u,v\rbrace$, $e' = \lbrace v,u'\rbrace$ be edges of an undirected graph $G$ and $ee'$ be the path from $u$ through $v$ to $u'$. The following defintions make sense for every graph ...

**1**

vote

**0**answers

75 views

### Toroidality testing

Is there a standard test for the recognition of toroidal graphs?
I have been using the Boyer-Myrvold algorithm (which has a MATLAB implementation) and would like to know if there is something ...

**1**

vote

**0**answers

65 views

### Self complementary cartesian products

Given two graphs $G$ and $H$ is there a nice way to check whether the cartesian product $G\Box H$ is self complementary without directly computing its complement and searching for isomorphism? For ...

**1**

vote

**0**answers

115 views

### Spectrum of Combinatorial Laplacian

The spectrum of the combinatorial laplacian is well understood for a square lattice. What about for other lattices?
In particular:
Let $ f: \mathbb{Z}^2 \rightarrow \mathbb{R} $. The usual ...

**1**

vote

**0**answers

108 views

### Kernel of modified Kronecker sum

The Kronecker sum of two matrices $A \in M(n \times n, \mathbb{R})$ and $B \in M(m \times m,\mathbb{R})$ is defined by the matrix
$$A \oplus B = A \otimes I_m + I_n \otimes B \in M(nm \times nm, ...

**1**

vote

**0**answers

151 views

### Relation between two different definitions of deficiency of a graph.

From Lovasz's Matching Theory,
Let $G$ be a bipartite graph with
bipartition $(A, B)$. For $X \subset
> A$, define $def(X) :=|X|-|\Gamma(X)|$, where $\Gamma(Χ)$
denote all points in $V(G)$ ...

**1**

vote

**0**answers

64 views

### Is every k-traceable d-regular oriented graph of order 2k traceable?

This problem is a special case of the traceability conjecture for oriented graphs.
For more information on this conjecture see the paper: "Progress on the Traceability Conjecture for Oriented ...

**1**

vote

**0**answers

145 views

### Grothendieck Constant of a graph and approximation limits

Let $K(G)$ be the Grothendieck constant of a graph with adjacency matrix $A$. How is $K(G)$ precisely related to approximation limits for some standard NP complete problems such as Chromatic, ...

**1**

vote

**0**answers

115 views

### Build minimum number of spanning trees to cover all nodes in a graph as leaves

Given a connected undirected graph $G = (V,E)$, where each node has a minimum degree of $d$, find the minimum number $N$ such that there exists $N$ spanning trees $T_1, ..., T_N$, where for each node ...

**1**

vote

**0**answers

99 views

### Graph theory: subset-simulation. Has already been studied under different names?

Hello,
this is my first question, I hope it will be clear and correct enough.
I am looking for a way to compare graphs in order to create a partial order among them (based on some kind of subgraph ...

**1**

vote

**0**answers

123 views

### the set of “Random Cartesian Product” of graphs

If $G= (V(G), E(G))$ and $H=(V(H), E(H))$ are graphs.
Consider the set $\mathfrak{R}(G,H)$ of "Random Cartesian Product" whose member are graphs $K =(V(K), E(K))$ defined as follow:
$V(K)$ = $V(G)$ ...

**1**

vote

**0**answers

81 views

### special 1-factorization of regular bipartite graphs

Let $n= 2k+1, |X|=|Y|= n$ and $G= (X, Y, E)$ be a $(k+1)$-regular bipartite graph.
Let $M $ be a perfect matching of $G$ having ...

**1**

vote

**0**answers

63 views

### An MST-like problem with vertex selection

Consider a planar pointset in a rectangle, where every point has a color (an integer label).
We need to select one point of every color, so as to minimize the cost of a planar MST of selected points ...

**1**

vote

**0**answers

219 views

### graphs with maximal number of paths of given length

Hi,
For a given number of edges, the non directed graph which maximises the number of paths of length 2 is the quasi-star or the quasi-complete graph.
Does anyone know :
1- what is the non directed ...

**1**

vote

**0**answers

221 views

### Gromov-Hausdorff convergence for locally finite spaces

Update: I've edited the question, since maybe it was a bit confusing and it's better to start with a more basic question.
I'm looking for properties of Gromov-Hausdorff convergence in the particular ...

**1**

vote

**0**answers

143 views

### Proof technique for packing constant-size paths with degree constraints in a tree with a perfect matching

For my research I am interested in finding disjoint copies of certain "good structures" in graphs which are trees with a perfect matching. So let $T$ be a tree with a perfect matching $M$. I am ...

**1**

vote

**0**answers

544 views

### About Hadwiger's conjecture

Hello,
last night I read the article of Wikipedia about Hadwiger's conjecture, and I found this open problem really interesting. In this article it is written that "in a minimal $k$-coloring of any ...

**1**

vote

**0**answers

216 views

### Modern books about orders and algebras on trees

Please help to find books about orders and algebras on trees.
If there is no modern books, please advice good old ones!
I'm more interested in finite trees (my current problem), but infinite ones are ...

**1**

vote

**0**answers

120 views

### Number of ways to separate a terminal from labelled vertices in a graph

I have a question about the number of different ways to separate a terminal vertex from labeled vertex sets in a simple graph. There is a bound on this number that I am interested in. I have succeeded ...

**0**

votes

**0**answers

20 views

### “Mutant knots” generalizable to “mutant tangled graphs”?

Just in case: Take a link L (drawn into the plane with over- and undercrossings),
draw a closed loop C on it which cuts L in four points, rotate the inside of C
around 180° (align the cut points on ...

**0**

votes

**0**answers

133 views

### Induced graphs of cayley graph

I have a Cayley graph $Cay(G,S)$, its group presentation $G=< S | R >$ and it is a metric graph by assigning a length equal to 1 to each edge. I also have an induced subgraph of that Cayley ...

**0**

votes

**0**answers

38 views

### Preferential Attachment and salton similarity in directed networks

Preferential Attachment similarity between two nodes in an undirected graph is the degree of the first node multiplied by the degree of the second node. But what about directed graphs? Which degree ...

**0**

votes

**0**answers

40 views

### Almost symmetric route in digraphs

Let $D=(V,E)$ be a digraph. A route of length $k$ in $D$ is a pair $L=(S,\sigma)$, where $S=(s_1,s_2,\dots,s_{k+1})$ is a sequence of $k+1$ elements of $V$, and ...

**0**

votes

**0**answers

36 views

### labeling graph of positive weighted vertices

is there a polynomial solution for the below problem? is it similar to a known problem in graph theory?
Given a directed graph G with cycles such that:
• G has a start node s with a path to every ...

**0**

votes

**0**answers

74 views

### The largest size of a boolean subgraph (a hypercube) of a given graph

Let $G(\mathbb{F}_2^n)$ denote the graph that represents the lattice of all subspaces of $\mathbb{F}_2^n$ (also called a Hasse diagram). I am interested in knowing if there exists a large hypercube ...

**0**

votes

**0**answers

49 views

### A particular method of removing edges from strong di-graphs

I have been mulling over a little puzzle I gave myself involving a particular type of iterative removal of edges from a digraph and I'm stuck -- thought I'd consult experts.
Start with an ...

**0**

votes

**0**answers

104 views

### What is the number of connected subgraphs with $n$ vertices of a labelled connected simple graph with $n$ vertices?

Suppose $G$ is a connected simple labeled graph. Let $n$, $e$, and $k$ be its number of vertices, edges, and the upper bound of the degree of a vertex, respectively. How many connected sub-graphs ...