Reputation
2,386
Top tag
Next privilege 2,500 Rep.
Create tag synonyms
Badges
12 30
Impact
~59k people reached

Jan
16
comment Applications of Prüfer sequence
If you count theoretical applications as well then it allows one to prove that the complete graph on $n$ vertices has $n^{n-2}$ spanning trees (Cayley theorem)
Jan
7
awarded  Nice Question
Dec
12
awarded  Yearling
Dec
9
comment Are there any vertex colouring algorithms which colour regular graphs optimally?
Not in general but if this is meant to be practical then a integer program may work well if your graphs are not too large
Dec
6
revised A triangle-free, 6-chromatic graph with 44 vertices
added 1 character in body
Dec
5
comment Eigenvalues of graphs
The trace of $A_G$ corresponds to the sum of its eigenvalues. Since $\rm{tr}{A_G} = 0$ it follows that any graph with at least one edge must have a negative eigenvalue
Dec
5
revised A triangle-free, 6-chromatic graph with 44 vertices
added 135 characters in body
Dec
5
revised A triangle-free, 6-chromatic graph with 44 vertices
added 135 characters in body
Dec
5
answered A triangle-free, 6-chromatic graph with 44 vertices
Dec
2
comment how to construct non-Hamiltonian graphs
Simply make them disconnected. Take for example The six cycle $C_6$ with degree sequence $(2,2,2,2,2,2)$ and two disjoint 3-cycles $C_3 \cup C_3$ which has the same degree sequence.
Nov
29
comment Graph Automorphisms and Induced Subgraphs
A first natural question in this direction is (analogous as for the orbits) whether almost all graphs have a trivial partition under $\sim$. If this is true (which I'd say it is) then there is not much you can say in general if you're given $\sim$
Nov
26
comment Comparison of Graphs (Adjecency List/Matrix)
Isomorphism software is already available in the form of libraries (nauty, bliss) and if you don't care about the interface I'd recommend using Sage. Implementing a good isomorphism tester from scratch might be overkill
Nov
26
comment Comparison of Graphs (Adjecency List/Matrix)
Perhaps I misunderstand but to me it seems that you need to test these molecules for isomorphism? Is this question of a theoretical nature or do you need to do this in practice?
Nov
25
revised Graph Isomorphism for non-mathematician
added 54 characters in body
Nov
25
comment “List all non-isomorphic trees with exactly 6 vertices”
A good way would be to list all trees of diameter 2, 3 , 4, 5.
Nov
25
answered Proof that Paley Graphs are strongly regular with parameters $(p,\frac{p-1}{2},\frac{p-5}{4},\frac{p-1}{4})$
Nov
23
awarded  Popular Question
Nov
22
revised Graph Isomorphism for non-mathematician
edited body
Nov
22
answered Graph Isomorphism for non-mathematician
Nov
22
comment Graph Isomorphism for non-mathematician
Perhaps this answer helps cs.stackexchange.com/questions/7690/…