Search Results

Results tagged with Search options user 3723
15 results

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, topological-graph-theory, random-graphs, graph-colorings and several others.

A tree decomposition of a graph $G$ is commonly defined in terms of a tree $T$ with the following structure: Each vertex $t \in V(T)$ is associated to a set $X_t \subseteq V(G)$; The union $\display … asked Feb 1 '13 by Niel de Beaudrap I'm going to suggest an approach to transitive closures which will yield the usual definition, in the special case of a 'simple' digraph having an adjacency matrix with entries in {0,1}. Namely: the t … answered Sep 29 '10 by Niel de Beaudrap 0answers I was wondering if the following decomposition of graphs has been studied, whether it has a name, and what the literature might be on it. Given a labelled graph G, we decompose its edge-set as a symm … asked Sep 21 '11 by Niel de Beaudrap In a similar spirit to David Eppstein's answer, one can relate this construction to the tensor product (a.k.a. the Cartesian product) of graphs and digraphs. If it is a standard construction, I'm not … answered Jun 30 '10 by Niel de Beaudrap 1answer What are the best results for upper bounds on the number of colours required in a strong vertex colouring of a regular hypergraph H? A regular hypergraph is one in which every vertex is contained in … asked Sep 15 '10 by Niel de Beaudrap As indicated by Felipe (primarily in his responses to my comments of his solution above), the problem is actually easy modulo a prime$p > 3$. Here I outline an explicit random poly-time solution, dep … answered Mar 13 '10 by Niel de Beaudrap 3answers I'm looking at algorithms to construct short paths in a particular Cayley graph defined in terms of quadratic residues. This has led me to consider a variant on Lagrange's four-squares theorem. The … asked Mar 10 '10 by Niel de Beaudrap As an alternative to my earlier computational answer for particular graphs G, here is a worst-case description of the asymptotic growth of the minimum size of the integers Nj Let h be the sum of |V( … answered Mar 26 '10 by Niel de Beaudrap The answer is "yes": there is such a family of$F$functions. In fact, a single computable function, acting on a single integer argument, suffices. We may do this by storing essentially complete infor … answered Mar 14 '10 by Niel de Beaudrap This question sounds more like a research project than a definite problem. Part of the reason for me to say this is because this question is only interesting if you impose some (ill-defined) qualifica … answered Mar 24 '10 by Niel de Beaudrap 4answers I suspect that a topic such as this may have been considered before: if so, I hope that someone can point me to a reference on the subject. I have a graph G with an upper bound d on its maximum degre … asked Sep 3 '10 by Niel de Beaudrap I'm not sure this qualifies as an answer, but I hope these remarks are useful to you; they re-present your problem in a format which is likely to be answerable by experts in discrete optimization. Th … answered Mar 25 '10 by Niel de Beaudrap 0answers Consider two different infinite graphs, whose vertices are drawn from$\mathbb Z^2$or$\mathbb Z^3$. Let$P_d : \mathbb Z^d \times \mathbb N \to \mathbb N$for$d \in \{2,3\}\$ be the function such th …