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

3
votes
0answers
183 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
0answers
174 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
0answers
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
0answers
234 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
0answers
235 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
0answers
295 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
0answers
203 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
0answers
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
0answers
393 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
0answers
401 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
0answers
98 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
0answers
80 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
0answers
94 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
0answers
44 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
0answers
47 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
0answers
64 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
0answers
58 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
0answers
68 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
0answers
53 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 ...
2
votes
0answers
74 views

What is the significance of the median eigenvalue?

When I look at the spectral density plots of my (usual) laplacian graphs, they spike at the median eigenvalue. But what significance for the graph/matrix (which originates from a network) does the ...
2
votes
0answers
128 views

Connected graph as connected space

Let $G$ be locally finite graph. By $|G|$, we mean the Freudenthal compactification of the 1-complex $G$, see chapter 8 of "Graph Theory" by Diestel. It is followed from Lemma 8.5.4 of Diestel's book: ...
2
votes
0answers
81 views

Minimum number of perfect matchings in a regular bipartite graph

Is there a lower bound on the number of perfect matchings in a $k$-regular bipartite graph? One can use Hall's marriage theorem and induction on $k$ to derive the lower bound of $k$. I can't come up ...
2
votes
0answers
34 views

“drift” of a random graph $G(n,p)$ with $p=\alpha\ln{n}/n$

Suppose $G\sim G(n,p)$ with $p=\alpha\ln{n}/n$ for some large constant $\alpha$. I wish to show a certain "drift" property of $G$, which can roughly be phrased as follows: if $u$ is "not that far" ...
2
votes
0answers
49 views

Weighted graph similarity

I have the following problem. Consider an undirected biconnected graph with $n$ vertices and $m$ edges ($n \leq m \leq n(n-1)/2$). The $m$ edges of the graph are then "populated" by integer weights ...
2
votes
0answers
71 views

Problems Solvable/Decidable by Counting Shortest Paths in Graphs

This questions is based on a dispute, whether it would be possible to calculate 'nice' routes in Manhattan, if the road network is assumed to be a rectangular grid and, that 'nice' means that there is ...
2
votes
0answers
88 views

second smallest eigenvalue Laplacian - submodular set function

Let $G$ be a connected unweighted undirected graph. In addition, let $\lambda_2(L(G))$ be the second smallest eigenvalue of the Laplacian matrix of graph $G$. Is $\lambda_2(L(G))$ a submodular set ...
2
votes
0answers
70 views

When polynomial GI implies polynomial (edge) colored GI?

(edge) colored graph isomorphism is GI which preserves the colors (of edges if it is edge colored). There are several reductions using transformations/gadgets of (edge) colored GI to GI. For edge ...
2
votes
0answers
55 views

Looking for similar centrality measurement on graph

I'm working on a graph problem somehow related to centrality measurement. Given an undirected, unweighted tree $T$ and a vertex $v$, let $D_i(v)$ be the set of vertices in $T$ that are i hops from ...
2
votes
0answers
73 views

Properties of a smallest tournament with domination number $k$

For some tournament $T$, let $\gamma(T)$ denote the cardinality of a smallest dominating set of $T$. Denote by $f(k)$ the minimum number of vertices of a tournament $T$ having $\gamma(T) = k$. From ...
2
votes
0answers
197 views

Computing the chromatic polynomial of graph modulo $x-3$

The chromatic polynomial of graph $P(G,x)$ is univariate polynomial which counts the number of colorings of $G$ with $x$ colors for natural $x$. Graph is not $k$ colorable iff $P(G,k)=0$. The ...
2
votes
0answers
52 views

Regular graphs with unimodal subdegrees that are not distance-regular

Distance regular graphs are known to exhibit the following property: starting from an arbitrary vertex $\alpha$, let $k_i$ denote the number of vertices at distance $i$ from $\alpha$ (in terms of ...
2
votes
0answers
76 views

Characterize the equivalence class of bipartite graphs obtained from each other by elementary row operations on their adjacency matrices

Let $M$ be an $m\times n$ matrix real matrix. Let $G$ be a bipartite graph, with partitions $A$ and $B$, such that $|A|=m$ and $|B|=n$. A node $i\in A$ is linked to a node $j\in B$ if and only if ...
2
votes
0answers
90 views

What is the projective dual of a planar graph?

Everybody learns the usual definition of the dual of a planar graph when edges are preserved and faces are mapped to vertices. Everybody learns the projective duality. What if we apply it to a ...
2
votes
0answers
59 views

Smallest distribution of points with genuinely different clusterings

An hierarchical clustering algorithm for (finite) sets of points in a given metric space is essentially determined by its linkage criterion, which defines the distance between arbitrary (finite) sets ...
2
votes
0answers
93 views

Proofs about Forbidden Minors

I am working on a problem which involves proving that a particular graph is a forbidden minor of the class of graphs that i am working on. Now i read kuratowskis theorem for planarity but i still ...
2
votes
0answers
114 views

Is there an universal (dis)similarity measure between two structures?

I'm always wondering is there an universal (dis)similarity measure between two structures (let's say between two undirected simple graphs)? I mean, not "the measure with universal parameter that we ...
2
votes
0answers
54 views

Minimal set of 2-2 Pachner move null sequences on a (nonplanar) trivalent graph?

A "null sequence" is of course a sequence of Pachner moves (inside a closed area) that doesn't change the trivalent graph. E.g. doing the same Pachner move twice (leads to orthogonality of 6j symbols) ...
2
votes
0answers
88 views

Counting regular Hypergraphs

The problem of counting regular graphs on $n$ vertices is notoriously hard. It seems like counting regular hypergraphs on $n$ vertices should be much easier (I am placing no uniformity condition). ...
2
votes
0answers
102 views

Hamiltonian Matroids

Similar to graphs, a Matroid $M$ is said to be Hamiltonian if there is a base $B$ of $M$ and $e \in M-B$ such that $B + e$ is a cycle of $M$. Is there any literature on this? EDIT: Actually my ...
2
votes
0answers
142 views

If two graphs have same Laplacian spectrums, are they the similar graphs?

If graph A and graph B have exactly the same Laplacian spectrums, can I just say they are same graphs? (only with scaling edge weights and node index reordering) I don't know if there is any explicit ...
2
votes
0answers
142 views

The Turán problem for graphs with given chromatic number

The ordinary Turán problem for graphs asks, "Given a graph $H$, if $G$ is an $H$-free graph on $n$ vertices, what is the largest number of edges that $G$ can have?" As is well known, if $\chi(H) = r ...
2
votes
0answers
232 views

On the existence of Graph Monomorphism

A graph monomorphism is an injective graph homomorphism. Determining existence of Graph monomorphism between graph pairs is computationally hard. Assume we talk only about classes of undirected ...
2
votes
0answers
114 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 ...
2
votes
0answers
93 views

Groups acting on non-locally-finite trees with independence and specified local actions

Suppose I have a biregular tree $T_{m, n}$ (not necessarily locally finite), with distinct cardinal numbers $m, n$, so Aut$(T_{m, n})$ acts on $T_{m, n}$ without inversion. Let $V_m$ be those vertices ...
2
votes
0answers
289 views

Why the number of the vertices is even?

Let $G$ be a graph with $n$ vertices and $V$ the vertex set. Suppose that for each non-empty subset $W$ of $V$ there exists an element $\omega \in V$ ( maybe in $W$ or not) such that the degree of ...
2
votes
0answers
95 views

A surjective graph homomorphism between 4-valent graphs

Let $K$ and $L$ be $4$-valent planar graphs with Euler circuits (where the choice of the next edge in the circuit consists of the edge which does not share a face with the edge before), with $|V(K)| = ...
2
votes
0answers
92 views

Reachability in dynamic random graphs

There has been some advice on how to ask questions. So I reask my question.I have a problem related to graph theory, random graphs or random geometric graphs in special that really confuses me. ...
2
votes
0answers
73 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$. ...
2
votes
0answers
55 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 ...
2
votes
0answers
118 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 ...