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

1
vote
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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
0answers
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 ...