# Tagged Questions

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, ...

66 views

### Is the chromatic number of the graph of the permutahedron known?

The permutahedron $\Pi_n$ is the polytope that is the convex hull of all permutations of the vector $(1,2,...,n)$. There are many results on its structure, but I couldn't find a result on the ...
34 views

I have a certain finite (but huge and without an apparent pattern, so that only numerical studies seem feasible) graph $G = (V,E)$, and a function $f: V \rightarrow \mathbb{R}$. On each edge $e = (u,v)... 0answers 73 views ### Hypergraph edge colouring I'm interested in knowing if finding the edge-chromatic number of a$k$-uniform$k$-partite hypergraph is NP-hard for$k\geq 3$Could anyone provide a reference for the result? By edge-chromatic ... 0answers 90 views ### What is the complexity of finding a third Hamilton Cycle in cubic graph? According to Smith Theorem: if a cubic graph has a hamilton circuit then it must have a second one. SMITH : Given a Hamilton circuit in a 3-regular graph, find a second Hamilton circuit. It is known ... 0answers 49 views ### Number of Hamiltonian paths in the Hoffman-Singleton graph/Moore graphs? Does anyone happen to know how many Hamiltonian paths are in the Hoffman-Singleton graph, or have any idea on how I could count such paths? 0answers 99 views ### Systematic treatment of folding and valued graphs I'm going to say beforehand that this question has something of a "am I missing something?" flavor. I'm in that odd position mathematicians often find themselves, where a topic has been addressed ... 0answers 76 views ### Graph adjacency grouping with geometric criteria I start with a list of adjacent tetrahedra, where there are tight seals to one another along faces for two tetrahedra that are adjacent. The vertices belonging to these faces for both tetrahedra are ... 0answers 80 views ### Is there a Havel-Hakimi for geometric graphs? Suppose that we are given$n$points in the plane, with a degree prescribed for each, and the question is whether we can place a geometric graph on them. Is there an efficient algorithm for this? ... 0answers 130 views ### Finiteness for 2-dimensional contractible complexes While thinking about graph-complex and related operadic stuff, I found a quite interesting (at least for me) question. However, I'm a novice in the algebraic topology, so I'm unable to resolve it by ... 0answers 107 views ### Construction of algebraic curves using line bundles on graphs In this paper http://arxiv.org/abs/0707.1309 Matthew Baker and Serguei Norine, construct a analogue of the Riemman Roch formula for Lineal Systems defined on graphs. In the paper http://arxiv.org/abs/... 0answers 127 views ### In a random graph which one is more probable,$k$-clique or$k$-core? Recall that the$k$-core of a graph$G$is the unique maximal subgraph of$G$with minimum degree at least$k$. In an Erdos-Renyi random graph, where the edge selection is independent with ... 0answers 107 views ### Group Travel Salesman Problem For the following Group Traveling Salesman problem, I'd like to know if there exists some poly-time approximation algorithm with constant approximation factor. Group TSP is defined as follows: Take a ... 0answers 139 views ### Edit distance vs. canonical adjacency matrix distance Let$G$and$G'$be two simple random graphs on the same set of nodes. Let$d_{edit}$be the edit distance between$G$and$G'$. Let$\mathbf{A}$and$\mathbf{A'}$be the adjacency matrices of the ... 0answers 104 views ### Synonyms for “labeling” of a graph In Preprint 1 we write numerical labels 0 or 1 at each vertex of a Dynkin diagram$D$. We call it a labeling of the graph (Dynkin diagram)$D$. In Preprint 2 we consider an extended (affine) Dynkin ... 0answers 104 views ### The degree/diameter problem for even girth graphs starting with upper bound I posted this on stackexchange but due to a lack of response there I am posting here. Let$G$be a graph with girth$g$, minimal degree$\delta$, maximal degree$\Delta$, and diameter$D$. Define $$... 0answers 99 views ### Does this notion of “\mathcal{F}-digraph” appear in the literature? By a digraph, I mean a quiver with no multiple edges. So in particular: Loops are okay. An infinite set of vertexes is okay. Furthermore, I will tend to identify each digraph with its underlying ... 0answers 63 views ### Small degree vertices in an epsilon-tough graph We say that a graph is t-tough if by deleting a set if vertices S, the resulting graph will have at most |S|/t connected components. We say that a graph is minimally t-tough if the deletion of an ... 0answers 72 views ### The Class of Strong Resolving Graphs of Hamiltonian Outerplanar Graphs I'll start with a couple important definitions. I'm not sure how well-known any of them are. Firstly, if G is a graph, and u, v \in V(G), say that u is maximally distant from v, denoted u\ ... 0answers 153 views ### Polynomial-time algorithm solving approximately a generalization of the travelling salesman problem Take a graph G and a number of sets of nodes of G. The problem is to find the shortest path passing through at least one node in each node set. If each node set consists of only one node, the ... 0answers 67 views ### Is the size of maximum matching in vertex transitive 3-uniform hyper-graph on n vertices always \Omega(n)? What is the best known lower bound on the size of the maximum matching in a vertex transitive 3-uniform hyper-graph? 0answers 183 views ### Characterizing graphs with k edge-disjoint minimum diameter spanning trees Henneberg [1] and Laman [2] characterized graphs which have, after adding any edge, 2 edge-disjoint spanning trees. This was generalized to k edge-disjoint spanning trees by Frank and Szegõ [3]. ... 0answers 170 views ### What mathematical models can analyze and optimize systems based on gossip? I look for a mathematical model that can accommodate, analyze and suggest optimizations for a system that can be humanly described as people gossiping about stuff. System description: We have a ... 0answers 260 views ### The Bilu-Linial conjecture and Ramanujan graphs The Bilu-Linial conjecture claims that every d-regular graph has a 2-lift such that for the signing matrix has its eigenvalues between [-2\sqrt{d-1},2\sqrt{d-1}] (the signing matrix" is the ... 0answers 98 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 ... 0answers 79 views ### Different definitions of linkless graphs Robertson, Seymour and Thomas defined linkless embeddings of graphs as follows: An embedding of G is linkless if every pair of disjoint circuits of G have zero linking number (see here). However ... 0answers 52 views ### Algorithm to construct metric space endomorphism with controlled square Given a finite metric space (M,d) with parameters K \geq 1 and \epsilon > 0, I'd like to algorithmically check for the existence of a non-identity map \phi:M \to M which happens to be K-... 0answers 98 views ### Node covering in a random graph Given N nodes randomly placed in a D\times D area, i.e., the position of each node is randomly chosen. Assume that both N and D are sufficiantly large. An agent can move in the area at ... 0answers 70 views ### Maximal k-chordal subgraph Recall that a graph is called k-chordal if any cycle C of length > k contains a chord, i.e. an edge joining to non-consecutive vertices in C. Let f(n, k) be the minimal number of edges s.... 0answers 88 views ### Reconstructing a function from its variants that negate one argument Call two functions g(x_1,\ldots,x_n) and h(x_1,\ldots,x_n) from complex numbers to complex numbers equivalent if they are the same up to the order of their arguments. Formally: there is a ... 0answers 159 views ### Must distinct tree eigenvalues be relatively far apart? How close to each other can two distinct eigenvalues of a tree be, as a function of the number n of nodes ? For example, the path P_n exhibits a gap of order \frac{2\pi^2}{n^2} asymptotically ... 0answers 44 views ### Balancing out edge multiplicites in a graph Let G be a multigraph with maximum edge multiplicity t and minimum edge multiplicity 1 (so that there is at least one 'ordinary' edge). Is there some simple graph H such that the t-fold ... 0answers 121 views ### When is an induced subgraph of a Johnson graph hamilton-connected? The Johnson graph J(n,k) has vertices which are the k-subsets of \{1, 2, \dots, n\} where two vertices are adjacent iff their intersection has size k-1. A graph is hamilton-connected if every ... 0answers 195 views ### vertex transitive and Cayley graphs (all the graphs alluded to below are finite). Suppose I gave you a graph, and asked you whether it was vertex-transitive. How hard is that algorithmically? The second question is: suppose I gave you ... 0answers 206 views ### Partitioning a cubic graph into two induced cycles of equal order I am aware that deciding the existence of a partition of the vertices of a connected graph G(V, E) into two induced cycles is NP-complete(Theorem 2). Induced cycle is a cycle without any chord (... 0answers 187 views ### Hitting edges in graphs at random and let them die with honor Let G=(V,E) be a finite simple 2-connected graph. Let B\subseteq E be a set of bad edges of size k:=|B|. For each edge e\in E we toss a fair coin (p=1/2) and if the outcome is head, we hit ... 0answers 79 views ### What is this expander-mixing-type graph property? Fix C>0. I am interested in graphs with the following mixing property:$$\Big|E(S,T)-\frac{1}{2}|S||T|\Big|\leq C\sqrt{|S||T|\max\{|S|,|T|\}}$$for every disjoint S,T\subseteq V. Note that ... 0answers 152 views ### Concentration inequality for function of independent Bernoulli r.v.'s (related to random graph) Consider a random undirected graph on a set of n nodes, say \{1,2,\ldots,n\}, such that the probability of edge between nodes i and j is p_{ij} (we may assume p_{ij}=o(1) for all i,j, i.... 0answers 189 views ### Bits required to encode difference between number of subgraphs with odd number of edges and number of subgraphs with even number of edges Let H = ( V, E ) be a k-uniform connected hypergraph, with n = |V| vertices and m = |E| hyperedges. Let O_w be the number of edge induced subgraphs of H having w vertices and an odd ... 0answers 305 views ### A problem on graph theory and complex numbers! Let {\mathcal G} = ({\mathcal V},{\mathcal E}) be a simple connected undirected graph with n vertices. Also let z_1, \ldots, z_n \in {\mathbb C} be complex numbers such that$$ ||z_1||=\ldots = |... 0answers 86 views ### Usefulness of polynomial ideals for graphs Given a graph$G=(V,E)$on$n$vertices, one can associate to it the polynomial$f \in k[x_1,\dots,x_n]$given by$f = \prod_{\{i,j\}\in E}(x_i - x_j)$. Then one can map various graph properties into ... 0answers 157 views ### Maximize weighted vertex sequence subject to neighbour inclusion Let$G=(V,E)$be a simple undirected graph on$n$nodes, with node weights$W = [w_1,w_2,\dots,w_n] \in \mathbb{R}^n$. Define the weight for a sequence of nodes$v_1,v_2,\dots,v_k$by the average$\...
243 views

I am seeking some reference on already existing work for the following problem. Given an $n$-dimensional square matrix $A=DP$ where $D$ is a diagonal and $P$ is a permutation matrix (think of Gaussian ...
67 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 ...
309 views

### How many trees can be constructed from k vertices using an LCA operator?

Consider the class of rooted trees and suppose I have at my disposal a lowest common ancestor (LCA) operator given by $$\textrm{lca}(u,v) = \text{the lowest common ancestor of u and v}$$ for all ...