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

1d
answered Is it possible to exist non-isomorphic (k,l) Ramsey graph?
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
30
accepted A matrix with a dense submatrix - application of Chernoff’s Inequality
Mar
25
awarded  Popular Question
Mar
13
answered How does the number of trees with even order that contain a perfect matching behave asymptotically?
Mar
12
revised Dihedral Groups…
added 3 characters in body
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
28
answered Does the leading eigenvalue of a connected undirected graph always increase with an edge addition?
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
24
answered Is there a nontrivial perfect vertex transitive graph?
Feb
18
answered Question about chromatic polynomial of certain graphs.
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))$