Jernej
Reputation
2,386
Top tag
Next privilege 2,500 Rep.
Create tag synonyms
 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/…