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

• 5 helpful flags
• 373 votes cast

# 255 Comments

 Apr 17 comment Is there a formula for the number of proper k-colorings of a graph $G$ up to isomorphism? @JossevanDobbendeBruyn One has to compute $\rm{Aut}(G)$. Hence, it seems to me, that this argument related to complexity invalid? In addition, the presented formula for all colorings is rather simple but it may contain exponentially many terms as well. Apr 10 comment Is the Wikipedia article about chordal graphs incorrect? $K_3$ is in fact chordal. Every cycle of length greater than 3 (none) has a chord (true) Mar 3 comment Does the leading eigenvalue of a connected undirected graph always increase with an edge addition? @M.Badaoui If a graph $G$ has two connected components $H_1$ and $H_2$ then the eigenvalues of $G$ are the eigenvalues of $H_1$ and $H_2$. Mar 2 comment Does the leading eigenvalue of a connected undirected graph always increase with an edge addition? No, not necessarily. In fact only if $k = 1$ and $G = K_2$ Feb 24 comment Is there a nontrivial perfect vertex transitive graph? @JohnSmith Not sure. I guess you can always take the line graph of a vertex transitive bipartite graph. Feb 18 comment On the eigenvalues of bipartite graph? There are 38 cubic bipartite graphs of order 16. Feb 17 comment On the eigenvalues of bipartite graph? I am pretty sure there is no general result in this direction. Considering just connected cubic bipartite graphs of order 16 for example (38) one can see that all but two have distinct (multi)sets of eigenvalues. 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.