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

Maximizing the minimum outdegree of digraph without $m$ cycle

Let $G$ be a simple digraph on $n$ vertices without a directed cycle of length $m$ (it may have directed cycles of length less than $m$. The cycles need not be simple). How large the minimum ...
2
votes
0answers
152 views

Structure of almost all bipartite graphs

I am studying some properties related to bipartite graphs and it would be useful for me to know if there is anything known about the structure of almost all bipartite graphs. For example, is it true ...
2
votes
0answers
161 views

A primal-dual (double) circle packing (coin graph) question

I know that any 3-connected simple planar graph with a designated outside face (outer face) has a primal-dual (double) circle packing (Brightwell-Scheinerman Theorem). Q1- But I am not sure whether ...
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
150 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
139 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
399 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
294 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
91 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
77 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
241 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
230 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
125 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
211 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
366 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
180 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
253 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
260 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
170 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
60 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 ...
1
vote
0answers
79 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
63 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
147 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
57 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
39 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
61 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
91 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
60 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
46 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
54 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
41 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
47 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
79 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
85 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
141 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
75 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
51 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
54 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
57 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, ...