Impact
~91k
people reached
- 0 posts edited
- 0 helpful flags
- 97 votes cast
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? |