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
189 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
220 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
123 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
254 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
332 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 ...
3
votes
0answers
248 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
306 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
210 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 \sum_{(...
3
votes
0answers
129 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
456 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
410 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
57 views

Induced matchings in a bipartite graph with every matching having the same number of edges

Suppose $n,k$ are positive integers such that $k\mid n$. Consider a bipartite graph $H=(A,B,E)$ such that $|A|=|B|=n$ and the edge set $E$ consists of the union of $m(H)$ induced matchings with every ...
2
votes
0answers
81 views

a continuous analogue of a graph theory question

I am reading a paper and it mentions a continuous analogue of a related graph theory question that people concern. The question is that suppose $E\subset Q=[0,1]^2$ has lebesgue measure $|E|>0$, is ...
2
votes
0answers
66 views

How are Polynomials of Toric ideals Studied with Exponents as ST-cuts?

Topic: Toric ideals on Expected value of Structure Functions in Random Graphs Goal: to understand the toric ideal where the exponents $h_i$ and $s_j$ are st-vertex-cuts of a digraph \begin{equation} ...
2
votes
0answers
63 views

Number of $(2n-1)$-edge-colorings of the complete graph $K_{2n}$

I just started reading about graph theory and have a question (which might be trivial). How many $(2n-1)$ edge colorings of $K_{2n}$ are there? A vaguer question: can I write $K_{4n}= K_4 + K_4 +.......
2
votes
0answers
50 views

Universal path function for all small trees

Let $f$ be a function $f: [k]^2 \rightarrow [k]$ (Where $[k]$ is the set $ \{0,1,\dots,k-1\}$). A function $f$ is called $n$-universal path function if for every tree $T$ with $n$ vertices there ...
2
votes
0answers
85 views

Maximum number of $4$-cycles

Suppose we have a balanced bipartite planar maximum degree $k$ graph. How many such graphs on $2n$ vertices have at most $f(n)$ maximum number of $4$ cycles for a given function $f:\Bbb R^+\...
2
votes
0answers
80 views

Regularity for a bipartite graph

Let $G$ be a bipartite graph with $2^n$ left vertices and $2^n$ right vertices such that: 1) degree of every vertex is not greater then $2^t$ 2) number of all edges is greater than $2^{n +t - O(\log ...
2
votes
0answers
58 views

When is the graph of cliques isomorphic to the graph itself?

Given a graph $G$ and the set $C_k(G)$ of the $k$-cliques in $G$, one can build a clique graph $H$ whose vertices $c_i\in C_k(G)$ are connected if the vertex sets of $c_i$ and $c_j$ have an ...
2
votes
0answers
135 views

Is the class of Heyting algebras originating from directed graphs a variety?

The category RefGph of reflexive directed graphs is the functor category $\hat{∆}_1=\mbox{Fun}(∆^◦_1,$Set), where $∆_1$ is the simplex category truncated at level 1. Hence the poset Sub(X) of ...
2
votes
0answers
85 views

Dicks–Dunwoody almost stability theorem

In the book 'Groups acting on graphs' (1989), Dicks and Dunwoody prove the following theorem (paraphrased): Let $G$ be a group acting on a set $E$, let $E'$ be a subset of $E$ and let $V$ be the set ...
2
votes
0answers
120 views

Detecting Negative Cycles in Undirected Graphs

I recently faced the problem of quickly detecting negative cycles in undirected, weighted graphs. Resorting to the Bellman-Ford Algorithm, as commonly suggested, turned out to be very inefficient and ...
2
votes
0answers
111 views

Formulating shortest path as submodular minimization

I'm curious about the general question of whether any combinatorial optimization problem with polynomial time solution can necessarily be reformulated as minimizing a submodular function. The answer ...
2
votes
0answers
123 views

Which functions preserve the connectivity of graphs/components?

I am somewhat stuck working on an issue and would really love some guidance. I will state the problem, my current state and what led to it in case the solution lies beyond where I was looking The ...
2
votes
0answers
71 views

Blossoms and Colorings

There is a striking analogy between finding maximum matchings in graphs and determining the chromatic number of graphs: both problems are fairly easy for bipartite graphs, but harder, resp. too hard ...
2
votes
0answers
59 views

Planar triangulations for which all distinct 4-colorings consist of exactly 6 Kempe chains

Are there any internally 6-connected planar triangulations other than the icosahedron all of whose distinct 4-colorings consist of exactly 6 Kempe chains, one for each of the 6 color-pairs? Addendum: ...
2
votes
0answers
52 views

The numbers of edge colorings and partitions into vertex covers

Let $G = \langle X \cup Y, E\rangle$ be a $d$-regular bipartite graph such that $|U|=|V|=n$, and assume that $d$ divides $n$. Let $F(G)$ denote the number of proper edge colorings of $G$ using $d$ ...
2
votes
0answers
283 views

Maps between graphs defined through laplacian operations

Edit: The views/answers ratio on this question tells me that it was too long. As such, I've stripped out examples and now ask the question in brief. For examples, please ask in the comments or look at ...
2
votes
0answers
73 views

Non-existence of commutative rings with many nilpotent elements with some restrictions where matrix powers are efficient

At the moment can't find better reference than "Cycle Enumeration using Nilpotent Adjacency Matrices with Algorithm Runtime Comparisons" though certainly there are others. Consider the following ...
2
votes
0answers
98 views

Obtaining a quasi-isometry of the 'boundary'

It is well-known that a quasi-isometry induces a homeomorphism on the space of ends of say a locally finite graph for simplicity. Clearly the converse is not true. In other words the concept of ends ...
2
votes
0answers
121 views

Classification of Automorphism set of a Regular graph

Let $A$ be the adjacency matrix of an $r$-regular graph $G$ with $n$ vertices (Not complete or cycle graph) . Also, let $Aut(G)$ be the set of all its automorphisms (i.e. set of permutation matrices)....
2
votes
0answers
66 views

Modularity in a graph - definition of the random component

This question concerns the definition of modularity in a graph. Consider a simple, undirected, unweighted graph $G$ with vertices in set $V$ and edges in set $E$ . Between any two vertices there is ...
2
votes
0answers
80 views

Even cycle constrained edge coloring

Is minimum colors needed to assign colors to edges of complete graph $K_n$ so that every $2t$ simple cycle where $t\in\Big\{1,\dots,2\Big\lfloor\frac{n}2\Big\rfloor\Big\}$ contains atleast $t+1$ ...
2
votes
0answers
106 views

From Planar Graphs To Tangent Circles

I have a conjecture: "For each planar graph with vertices $V_1, V_2,\ldots, V_n$ there exist disjoint circles $w_1,w_2,\ldots,w_n$ in the plane, such that for every $i,j$, $w_i$ is tangent to $w_j$ ...
2
votes
0answers
52 views

Maximum cardinality general factor of a graph

Given a graph $G=(V,E)$ and a set of integers $B(v)$ associated to each vertex, a general factor of $G$ is a set of edges $F\subseteq E$ such that the degree of each vertex $v\in V$ in the graph $(V, ...
2
votes
0answers
46 views

Is this infinite family of non-trivial snarks resulting from the first Celmins-Swart?

Non-trivial snark is cubic graph with chromatic index $4$, girth at least $5$ and doesn't to contain three edges whose deletion results in a disconnected graph, each of whose components is nontrivial. ...
2
votes
0answers
82 views

Decomposing a weakly chordal graph into disjoint union of co-chordal graphs

A graph G is said to be co-chordal if it is $\bar C_n$-free for any $n \ge 4$. It is weakly chordal if it is $C_n$ and $\bar C_n$ free for all $n\ge 5$. Assume that the induced matching number of $G$ ...
2
votes
0answers
66 views

Edge-disjoint path-systems in infinite digraphs

Let $ D=(V,A) $ be a directed graph without backward-infinite paths and let $ \{ s_i \}_{i<\lambda},U \subset V $ where $ \lambda $ is some cardinal. Assume that for all $ u\in U $ there is a ...
2
votes
0answers
52 views

Mappings between adaptive networks and Markov processes

Are there any known mappings between adaptive networks models (i.e. graph model representations of networks where the internal vertex dynamics and connectivity topology can change subject to specific ...
2
votes
0answers
31 views

Is it true that centrality measures in SNA are indicative for most important vertices only?

I read about the limitations of centrality measures on Wikipedia. It says that centrality measures are good only for identifying top most important nodes in a social network. Their relative values can ...
2
votes
0answers
130 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
90 views

Linear intersection number and coloring (not chromatic) number

A linear hypergraph is a pair $\pi=(X, L)$ where $X\neq \emptyset$ is a set and $L\subseteq {\cal P}(X)$ has the following properties: for $e\in L$ we have $|e|\geq 2$; if $e_1\neq e_2 \in L$ then $|...
2
votes
0answers
111 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
41 views

Isomorphic Hadwiger graphs of connected infinite graphs

Let $G$ be a graph, then we define its Hadwiger graph $\textrm{Hadw}(G)$ in the following way: $V(\textrm{Hadw}(G)) = \{S\subseteq (V(G): S\neq \emptyset\textrm{ and } S \textrm{ is connected}\}$; $...
2
votes
0answers
171 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 ...
2
votes
0answers
100 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
55 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
58 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
123 views

Cores of infinite graphs

Let $\kappa$ be a cardinal and let $\textrm{Grph}(\kappa)$ be the set of graphs $G = (V,E)$ such that $V \subseteq \kappa$ and $E \subseteq \mathcal{P}_2(V) := \{\{a,b\} \subseteq V: a\neq b\}$. We ...
2
votes
0answers
78 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 ...