Andrew D. King
Reputation
1,218
Top tag
Next privilege 2,000 Rep.
Edit questions and answers
Badges
11 14
Newest
Impact
~91k people reached

• 0 posts edited
• 0 helpful flags
• 97 votes cast

184 Actions

 Feb 19 revised Distribution of distances in permutations added 309 characters in body Feb 19 answered Distribution of distances in permutations Feb 7 comment complexity of dominating sets of regular graphs Dominating set is NP-complete, and even APX-complete, for cubic graphs. dx.doi.org/10.1016/S0304-3975(98)00158-3 Feb 5 comment Is the empty graph a tree? By the way, Jernej, when making contributions to Sage, boring technical questions are of the utmost importance, particularly when recursion is involved! Feb 5 comment Is the empty graph a tree? I agree, and would point out, in case anyone is uncomfortable with "disconnected" and "connected" not forming a dichotomy, that neither do "closed" and "open". Jan 15 comment Hypergraph Chromatic Number vs Degree, Clique-Size Just for the record, Bruce and I now have an easier proof of this theorem posted on arXiv, but it still uses a combination of structural and probabilistic arguments. Jan 12 awarded Organizer Jan 12 revised counting triangle free graphs edited tags Jan 11 comment If a graph invariant is NP-Hard, is its “deck ratio” NP-Hard as well? Perhaps it would be useful to insist that $\psi(G-v)$ cannot have the same value for all $v$. Jan 8 comment Coloring a graph by Maximum Independent Set extraction Yes, everything you are saying is correct. In these examples, notice that when we don't have a good colouring, it is because we take a maximum stable set that does not intersect every "hard to colour" region of the graph. In these cases the "hard to colour" region is a large clique, but you could also think of it as an induced subgraph with high chromatic number. The reason that Reed's approach gets a nice bound for the fractional chromatic number is that it doesn't just take any MIS, but rather it takes every MIS with equal probability. Jan 7 answered Coloring a graph by Maximum Independent Set extraction Dec 10 answered Shannon capacity determined by $\alpha(G)$ and $\chi^*(\bar{G})$??? Nov 26 answered Upper bound on Shannon capacity based on independence number Sep 10 comment number of totally different path between two nodes in graph theory As stated by Igor, you want biconnectivity. A naive way to check this is to check, for each vertex $v$, that $G-v$ is connected. Aug 21 comment How many mathematicians are there? @Pete Georgia Tech might single-handedly make Georgia an overachieving state, but even 10,000 seems low. Aug 21 comment How many mathematicians are there? The definition would also exclude Jack Edmonds. Aug 8 comment Is there any relationship between a tree(graph theory) and semi-metric? Let the distance between $x$ and $y$ be the square of the sum of the weights on the path between them. Then, as you can see with a path on three vertices where both edges have weight 1, the triangle inequality does not hold. Think of any semi-metric you can form on a subset of $\mathbb R^1$. Then you can form that on an edge-weighted path. Aug 7 answered How to partition a graph into N groups with M elements nearest? Jun 18 comment Is there a polynomial upper bound for number of holes over following class of graphs? No. Subdivide each edge. This leaves a triangle-free graph with Poly($n$) vertices, and at least as many holes. Jun 1 comment Regular graph of order 50, degree 7 and Automorphism group of order 288000. How to check if it is Cayley What is the structure of the subgraph induced by the neighbourhood of a vertex?