bio | website | andrewdouglasking.com |
---|---|---|
location | Vancouver | |
age | 34 | |
visits | member for | 5 years |
seen | 9 hours ago | |
stats | profile views | 1,291 |
I am interested in graph theory and combinatorial optimization.
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? |
May 29 |
comment |
An example of when nauty, on two different platforms, gives different canonical labels for the same input graph?
Is this comment tongue-in-cheek, or has the implementation somehow been verified using formal methods? (Or do you just mean, if such an example was known it would have been fixed?) |
Apr 25 |
awarded | Notable Question |