Reputation
2,260
Top tag
Next privilege 2,500 Rep.
Create tag synonyms
Badges
12 29
Impact
~55k people reached

Feb
1
comment Third coefficient of the chromatic polynomial
given that you know $a_2$ depdens on the number of triangles, your task is then to express $t$ in terms of $|V|,|E|$ and the number of independent sets of size $3$. I am not sure that's doable without also knowing the number of $2$-paths.
Feb
1
comment Non trivial results in graph theory/combinatorics coming from number theory
In this paper arxiv.org/abs/1011.3376 the authors use 3-term arithmetic progressions and related number theoretical results to obtain a bound on a certain edge coloring.
Feb
1
comment Third coefficient of the chromatic polynomial
What exactly are you looking for ? A proof of the stated identity for $a_2$?
Jan
28
comment Is there matrix representation of the line graph operator?
I am sorry I don't understand. You don't know how to prove this identity?
Jan
28
comment Is there matrix representation of the line graph operator?
I don't know if that helps bu you can express the adjacency matrix for the line graph by using the incidence matrix. If $E$ is the incidence matrix of your graph $G$ then $E^T E - 2I = A(L(G))$
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)
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
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
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
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
22
comment Graph Isomorphism for non-mathematician
Perhaps this answer helps cs.stackexchange.com/questions/7690/…
Sep
29
comment Counting spanning trees and hamiltonian paths
Yes but there are exponentially many ways in which you can do these exchanges.
Sep
2
comment Finding a function satisfying a certain inequality
Nice. Now that should already indicate that such function is not to be found right?
Sep
1
comment Finding a function satisfying a certain inequality
Thanks for the expanded answer. What is this telling us about the existence of $f?$ If I understand this bound does not imply that $f$ does not exist? Am I missing something?
Sep
1
comment Finding a function satisfying a certain inequality
I see. Does the lower bound actualy imply that there is no such function - don't we need to figure out what the $O(n)$ term is ?
Sep
1
comment Finding a function satisfying a certain inequality
Hm! What exactly is the function $f(n,k)$ here? Also the inequality should hold for all $p,k,l$ in the stated interval.
Sep
1
comment Finding a function satisfying a certain inequality
@StevenGregory Edited the latex part. Is there still anything that is unreadable?