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

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.