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

2
votes
0answers
167 views

What is the genus of a Johnson graph?

The Johnson graph $J(n, k)$ has a known genus when $k=1$, in which case it is the complete graph $K_n$. What can be said about the genus of $J(n, 2)$, or more generally $J(n, k)\ ?$
2
votes
0answers
112 views

Perfect P6-free graphs with further properties

Let $G$ be a graph without any hole or antihole of odd length at least 5 (i.e. $G$ is a Berge graph and so by the Strong Perfect Graph Theorem, $G$ is perfect). Assume further that $G$ has no ...
2
votes
0answers
149 views

Polyhedral embeddings of large face-width where all faces have the same length

Where can I find examples of polyhedral embeddings of simple graph with large face-width, such that all the faces have the same length? By polyhedral embedding I mean an embedding of the graph on a ...
2
votes
0answers
135 views

Additional Constraint Baum Welch for HMMs

I'm trying to derive a special form of the Baum Welch algorithm where there is an additional constraint that the sum of emission probabilities over all states sums to one for each output symbol. ...
2
votes
0answers
103 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 ...
2
votes
0answers
397 views

Matching in regular bipartite graphs

Let $G=(X,Y,E)$ be an $r$-regular bipartite graph where $|X|=|Y|$ . Let $\phi$ an automorphism of $G$ with $\phi(X) = Y$ and $\phi \circ \phi = id$, and let $\psi$ be the mapping induced by $\phi$ on ...
2
votes
0answers
285 views

Matrix Operations Preserving Hurwitz Stability

I begin with terminology I use in the question. A real square matrix $A$ is negative-stable if for every eigenvalue $\lambda$ of $A$, ${\mathrm{Re}}(\lambda) < 0$; $\ast$-negative-stable ...
2
votes
0answers
90 views

Graphs, non-Hausdorfness and Wallman compactifications of non-regular spaces

Given a non-Hausdorff space $X$, one can form a graph $G_X$: vertices the points of $X$, edges indicating point pairs not separated by open sets. Up to graph-theoretically (but not topologically) ...
2
votes
0answers
71 views

Subgraphs of bounded tree-width and preserving edges of original graph

Given a graph $G$, I would like to determine a method for randomly generating subgraphs $G'$ with the following properties: Each edge of $G$ has at least some probability $p$ of going into $G'$ The ...
2
votes
0answers
76 views

A non-distinct system of representative edges.

I have the following problem: Let $ \mathcal{G} = (G_{i})\_{i} $ be a collection of graphs. I would like to find a "system of representative edges" $ f : \mathcal{G} \rightarrow \bigcup_{i} E(G_{i}) ...
2
votes
0answers
239 views

Slightly improving bounds on two-color Ramsey numbers by globally pruning edges and counting connected vertices in instances of two-colored complete graphs

The two-color Ramsey number, $R(m, n)$, is the minimum number of vertices, $||V||$, in a complete graph necessary for there to exist a clique of order $m$ or an independent set of order $n$. In terms ...
2
votes
0answers
183 views

Maximum number of 4-colorings of planar graphs (precise version)

This is a redo of my earlier question. I'm trying again with more precision. I ignored one of the dicta in the "how to ask" page. For a fixed $n$, what is known (references preferred) about the ...
2
votes
0answers
229 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 ...
2
votes
0answers
124 views

$f$-vector of graph connectivity

For a connected graph $G$, let $N_i$ be the number of connected subgraphs of size $i$. The vector $\langle N_0, N_1, \dots \rangle$ is also known as the $f$-vector for the graph. As a superset of a ...
2
votes
0answers
201 views

Complexity of bipartite graphs and their matchings.

My question concerns a hypothetical family of bipartite graphs, $G_i$. Each graph $G_i$ has $2^i$ red nodes and $2^i$ blue nodes - so nodes get labelled by their color and a binary string of ...
2
votes
0answers
361 views

Hamiltonian paths in subgraphs of rectangular lattice graphs

Is following decision problem NP-hard / NP-complete: Having vertex-induced subgraph of rectangular lattice graph determine if any Hamiltonian path exists Having vertex-induced subgraph of ...
2
votes
0answers
179 views

Counting the independent sets of a comparability graph with maximum degree 3. Is it #P−complete ?

This question was first asked here: cstheory.stackexchange... Here we want to count the number of independent sets of a comparability graph. For Δ(G)=2 , i.e. the maximum degree of a vertex in G is ...
2
votes
0answers
191 views

Complexity of finding disjoint 2-factors with equal cardinality in cubic graphs?

Finding a connected 2-factor that contains every node in cubic graphs is $NP$-complete since it is equivalent to the Hamiltonian cycle problem. I'm interested in the complexity of finding vertex ...
2
votes
0answers
247 views

When is polytope compatible with network flow?

A linear program is the problem of optimizing an linear objective function within some polytope $A$ over $\mathbf R^n$. My question is motivated by the question of when a linear programming problem ...
2
votes
0answers
259 views

Connectivity in random points on a grid using a rope of fixed length.

This problem is a by product of another problem. I would like to restate this problem as a sort of a puzzle. Suppose we have a $l \times b$ grid. We select $k$ points on the grid randomly and ...
2
votes
0answers
222 views

Group of local complementation as a coxeter group

Can the group generated by local complementations, ${lc_i|i=1,\cdots,n}$ on simple graphs on $n$ vertices, be categorized as a coxeter group? After all these obey: \begin{equation} \langle lc_i| ...
2
votes
0answers
131 views

finding set of tree decompositions to cover all pairs of vertices

I first asked this on cstheory.SE but got no reply. Let $P(X_i=x)$ represent probability that randomly chosen proper $q$-coloring of an $L\times L$ square grid contains color $x$ at position $i$. How ...
2
votes
0answers
168 views

Semantics of neural network-like structures

Background Language (of mathematicians and most other people) has a sequential surface structure and a tree-like deep structure. So semantics usually is the semantics of such syntactical structures: ...
2
votes
0answers
259 views

Drawing a combinatorial 3-configuration of points and lines with pseudolines

This question is related to the question of drawing a combinatorial 3-configuration of points and lines with straight lines. We only relax the condition and admit drawings with pseudolines. Let us ...
2
votes
0answers
202 views

Term for the diameter of the complement of a graph?

Have you heard of one?
1
vote
0answers
64 views

Multiple Bipartite graphs and matchings

I've been told recently that it's better i just for help regarding my 'specific' problem rather than lots of little questions around the same topic which appear somewhat unclear. I would first like to ...
1
vote
0answers
58 views

Hamming graph and independent sets

I'm defining the Hamming graph $H(d,q)$ in the usual way, so we have a set $S$ of $q$ elements, the hamming graph $H(d,q)$ has vertex set $S^{d}$ (the set of all ordered $d$-tuples of elements of $S$) ...
1
vote
0answers
140 views

Threshold for perfect Matchings in Bipartite graph

Consider the random bipartite graph with vertex classes of size $n$ and each edge being present independently with probability $p(n)$. I know one way to prove the threshold of a perfect matching is ...
1
vote
0answers
54 views

Is there an elliptic Harnack equality for directed graphs?

The elliptic Harnack inequality for undirected graphs was proven by Delmotte in the paper "Inegalite de Harnack elliptique sur les graphes" (French, ...
1
vote
0answers
37 views

Rate of convergence of graph-theoretic quantity to fractional graph-theoretic counterpart

Let $G^n$ denote the OR product of a graph with itself $n$ times, i.e. the graph which has an edge between distinct vertices $(v_1,v_2,\ldots,v_n)$ and $(u_1,u_2,\ldots,u_n)$ if there exists some $i$ ...
1
vote
0answers
58 views

Matchings in random bipartite graphs

I was wondering if anyone could point me in the direction of a text or paper which would help deal with the following problem Suppose i am given a $K_{\mathrm{log}(n)} \times K_{\mathrm{log}(n)}$ ...
1
vote
0answers
83 views

NP hard problems on geometric graphs

I have posted this question before but i don't feel i expressed my confusion clearly enough. So i would like to try and explain again. This is a proof of the minimum vertex cover for unit disk graphs ...
1
vote
0answers
58 views

Max flow with minimal requirements algo problem

While applying the algorithm to solve the max flow of the network with minimal requirements on edges, I have encountered a problem. The algorithm states: For graph G create an edge from target to ...
1
vote
0answers
41 views

Solutions for n such that the path number to the n-th node is also n in a complete, rooted, ordered k-ary tree

The path to find the $n$-th node within a complete, rooted, ordered $k$-ary tree can be represented by a number to the base $(k+1)$ that contains no zero digits. See A245905 in OEIS as an example for ...
1
vote
0answers
52 views

clustering in a graph on boolean functions

Fix some n and k. Consider the following directed graph: vertices are all functions $2^n\rightarrow 2^n$ and a vertex f has an edge to a vertex g for every h such that $f=h\circ g$ and h depends only ...
1
vote
0answers
62 views

The number of blocks in Szemerédi Regularity Lemma

In mathematics, the Szemerédi regularity lemma states that every large enough graph can be divided into subsets of about the same size so that the edges between different subsets behave almost ...
1
vote
0answers
39 views

Recognizing bridgeless cubic graph with special 2-factor

A 2-factor of graph $G(V, E)$ is a set of vertex-disjoint cycles that cover $V$. It is known that every connected bridgeless cubic graph contains a 2-factor (and a perfect matching). I conjecture ...
1
vote
0answers
60 views

Is a rigid cycle a chordal graph?

There are two relevant questions: (1) We know an edge set $C$ is a rigid cycle in $\mathcal{G}_2(n)$ if and only if $|E(C)|=2|V(C)|−2$ and $|F|≤2|V(F)|−3$ for every proper subset $F$ of $E(C)$. Thus, ...
1
vote
0answers
38 views

How to restructure adjacency matrix $A$ from shortest distance matrix $B$ in Network topology inference

An undirected graph with $n$ nodes could be referred to as an adjacency matrix $A$. $A=[a_{ij}]_{n×n}$ with $a_{ij}=a_{ji}=1$ standing for there being an edge between node $i$ and node $j$, and no ...
1
vote
0answers
113 views

lower bound for difference between max cut and min cut

Let $G=(V,E)$ be a graph on $n$ vertices with edge weights $w=(w_e)_{e\in E}$. Let $M^+$ and $M^-$ be the maximum and the minimum cut values, i.e. ...
1
vote
0answers
77 views

Disks in Flat Embeddings of Graphs in $\mathbb{R}^3$

Robertson, Seymour and Thomas proved that any linkless graph $G$ has a flat embedding in $\mathbb{R}^3$ (see for example A survey of linkless embeddings). An embedding of $G$ is flat if for any cycle ...
1
vote
0answers
78 views

Possible ways to create a graph representation from a distance matrix (through approximation)

Forgive me, Im not math professional, but a computer scientist at the beginning of my base research from my thesis, so bare with me if I miss something blatantly obvious. I have a Euclidean distance ...
1
vote
0answers
132 views

Kempe chain color swaps in a partially colored map

Crossposted from math.stackexchange.com: http://math.stackexchange.com/questions/904932/kempe-chain-color-swaps-in-a-partially-colored-map Question: In this partially Tait's colored map, using ...
1
vote
0answers
74 views

Empty node in cactus construction

Is there a necessary condition for not having empty node in the construction of the cactus of the minimum cuts of a graph? In particular is there a necessary condition for not having empty k-junction ...
1
vote
0answers
117 views

Find a path that covers as many nodes as possible

I have the following interesting problem. Given a graph $G$, an agent starts to mark nodes in $G$ in the following way: it marks all nodes within distance $d$ from it. Now the question is to find the ...
1
vote
0answers
50 views

Simulation of disassortative random graphs

Recently I have been trying to find a succinct algorithm for generation of disassortative networks. The best I have found is the algorithm by Newman described in his paper "Mixing patterns in ...
1
vote
0answers
53 views

Polynomial problems in graph classes defined by forbidden induced cyclic subgraphs

Let $C$ be a graph class defined by a finite number of forbidden induced subgraphs, all of which are cyclic (contain at least one cycle). Are there graph problems that can be solved in ...
1
vote
0answers
56 views

Asymptotic results in unbalanced left $d$-regular expander graphs

Let $U = [n]$ and $V = [m]$ be sets of nodes with $n > m$ and $E = U\times V$ be a set of edges. Let $\mathcal{N}(S)$ be the set of neighbors of a subset $S$ from $U$ or $V$. Call a graph $G = (U, ...
1
vote
0answers
71 views

labeling vertices in a graph to minimize distance between adjacent vertices

We have a regular graph $G$ of degree $m$ on $n$ vertices and we label each of its vertices with the number $1$ through $n$. What can we say about the maximum difference between the numbers of two ...
1
vote
0answers
116 views

Relationship betwen eigenvectors

Suppose that we have two matrices A and B. Matrix B is taken from A with one row and one column deleted. On the other hand A is n*n matrix and B is (n-1)*(n-1) matrix and is created by deleting last ...