User shahrooz - MathOverflow

Answer by Shahrooz for Is there any proof that you feel you do not "understand"?

2013-05-17T13:13:31Z

"Edgar Allan Poe:" "Any cryptosystem that human invented are breakable." So, any proofs are understandable. However until now, the zodiac 340 letter (or 340 symbol code) is not cracked.

For me, these two problems were very outstanding:

$1)$ Suppose there are infinite number of points in a plane and the distances between each two point is an integer, then they are all on a single straight line. This problem proposed by Sylvester and the solution by Paul Erdős is very strange for me.

$2)$ For $n\geq 2r$, the chromatic number of Kneser graph $K_{(n:r)}$ is $n-2r+2$. When I studied the proof of this theorem again and again (and also I understood it), I found that I can not understand it much more.

Answer by Shahrooz for Quantum algorithms for dummies

2013-05-03T18:03:07Z

I think this book is good for beginning:

"An introduction to quantum computing algorithms" by Pittenger A.O.

Also, the course by Prof. $Vazirani$ on $edx$ "(www.edx.org)" is good way for learning the necessary material in this way.

Since, there are two main algorithms and other algorithms uses these basic algorithms, you can understand deeply these two quantum algorithms and modify your problem again to find an approach. These two basic and important algorithms are Grover's algorithm (for searching problem) and Shor's algorithm (for factorization). Also, Simons algorithm is good for studying. But, in general, you must learn Fourier sampling and superposition and the quantum gates and their works.

Answer by Shahrooz for Ramsey numbers and graph spectra

2013-04-23T16:31:07Z

Actually, I think you are right and there are not such papers that exactly match with your subject. But, some probabilistic techniques used spectral theory to find some bounds for Ramsey number. One of this paper is famous:

"Asymptotically tight bounds for some multicolored Ramsey numbers" by "Noga Alon" and "Vojtech Rodl"

So, if you change your keywords for searching based on this paper and its references, you might be more successful.

Also, the below paper is good:

"Extremal and Probabilistic Combinatorics" by "N. Alon" and "M. Krivelevich".

Answer by Shahrooz for Will quantum computing kill cryptography ?

2013-04-20T19:34:41Z

There is a very good book that you can find your answer there completely. This book's name is:

"Post-Quantum Cryptography" by "Daniel J. Bernstein, Johannes Buchmann and Erik Dahmen".

As a part of this book, today we know that these cryptosystems can be broken by quantum computers:

$1)$ RSA public key encryption

$2)$ Diffie-Hellman key-exchange

$3)$ Elliptic curve cryptography

$4)$ Buchmann-Williams key-exchange

$5)$ Algebraically Homomorphic

and these cryptosystems (and also with some variants) are safe:

$1)$ McEliece public key encryption

$2)$ NTRU public key encryption

$3)$ Lattice-based public key encryption

Also, the good cryptosystems is not usable today because of the storage space problem and complexity. We have some limit on quantum computers that help us to design some good cryptosystems. There are some problems that if we have very large quantum computer and the best quantum algorithm,still we need exponential time for solving them. For example, searching among very large database to find special data, is very hard problem for quantum computer. We can prove that if we have $N$ cases that there is only one suitable case, the best quantum algorithm need $O(N^\frac{1}{2})$ to solve it. Also, it is proved that there is not better result. So, we can hope that we can find some efficient algorithms against the power of quantum computer and quantum algorithms.

Mathematical Paper That Just Links Two Different Fields of Sciences

2013-03-28T12:24:58Z

I have a soft question that is interesting for me in some aspects. I appreciate your answers and comments about it.

Four years ago, one of my friends in MIT, in the biology lab, had working on neuroscience and specially he worked on Deja-Vu phenomenon. When he asked me about writing a program with Matlab for simulating this phenomenon with a network of cells that they want simulate the Sinc function, I found that there are many good theorems in graph theory that can be useful for his research. When I suggested him this idea, he found it very interesting.

My question are about this event in a little bit different way. Is it possible that we publish a paper in some mathematical journals that:

1) The only new thing in the paper is relation between a real phenomena and a field of mathematics that is well known. For example, we just model the controversy with bandwidth problem, and no more things just using the theorems that proved for bandwidth problem.

2) This paper does not have new theorems as like as theorems that are common in mathematical papers. This paper just use mathematical theorems in its direction.

Also, do we have some mathematical journals that publish such a papers? And if yes, is there some evidences for this type of publication?

Maybe someone think about the Hilbert Spaces and quantum mechanic. But, in my view, this is not the case. We use Hilbert spaces to model some aspects of quantum mechanics and we get some new results and theorems in quantum mechanic. If we want to think this relation, the paper only must be contain the modeling of quantum mechanic by Hilbert spaces and no more.

Briefly, suppose we found a connection between a real phenomenon and a field of mathematics that can be acceptable or a new view point for analysis the phenomenon. For example, if we found a relation between Darwin's evolutionary theory and a game on graph, is it possible that we can publish such a results as a paper in a mathematical journal? And what kind of mathematical journal is good for this work?

Sorry me for long question.

Answer by Shahrooz for Examples of interesting false proofs

2013-03-20T15:38:34Z

I think nobody point to these interesting false proof:

Let $i=\sqrt{-1}$ be the complex number.

$1)$ $1=\sqrt{-1\times-1}=\sqrt{-1}\times\sqrt{-1}=i\times i=-1$.

$2)$ We know that $x^\frac{2}{6}=x^\frac{1}{3}\Rightarrow (\sqrt{x^2})^\frac{1}{6}=(\sqrt{x})^\frac{1}{3}$. Now, let $x=-1$ and so we have: $$(\sqrt{(-1)^2})^\frac{1}{6}=(\sqrt{-1})^\frac{1}{3}\Rightarrow1=-1.$$

Answer by Shahrooz for Spectrum of a Laplacianized matrix

2013-02-07T18:03:09Z

It is just a point of view. But it is more long for writing it as a comment.

If $A$ be the adjacency matrix of graph $G$, then $R-A$ is its Laplacian matrix and there are some good bounds for the radius (or maximum eigenvalues of this matrix) of matrix. For example, if we denote the maximum eigenvalue of this matrix by $\mu$, we have: $$\mu\leq \sqrt(2)\times max(d(v)^2+\sum_{uv\in E(G)}{d(u)})^\frac{1}{2}$$ where $v$ changes in the vertices of the graph $G$. In most cases, we can extend such relations to the positive definite matrices. For more such bounds you can see the paper:

Bounds on the (Laplacian) spectral radius of graphs, written by $Lingsheng$ $Shi$ and published in Linear Algebra and Its Application.

But in general, as you want, I think there is not good bound.

Minimum sum among fixed length factors of a number

2013-01-19T21:17:37Z

I think this question is famous, but I searched a lot in the internet with many keywords and unfortunately I did not find any related problem. I will appreciate any helpful answers and any guidance for similar questions and problems.

Suppose the integers $n$ and $k$ are given and the set $S$ shows all possible factorization of the integer $n$ into $k$ factors. The factors of these factorization not necessarily primes and can be composite. Also, at most one factor can be the number $1$. For example, if $n=128$ and $k=3$, we have:

$S=\lbrace 2\times4\times16, 4\times4\times8, 2\times 2\times32, 1\times2\times64, 1\times4\times32,1\times8\times16\rbrace$.

For fixed numbers $n$ and $k$ (and also the set $S$), let $m\in S$ and $m=l_1\times l_2 \ldots\times l_k$. We define $S(m)=\sum_{i=1}^k{l_i}$.

What can we say about the minimum of $S(m)$, where $m$ changes in the set $S$? Do we have any formula for finding this minimum respect to the $n$ and $k$?

For the above example, the minimum is happen for $m=4\times4\times8$ and $S(m)=16$.

Is this a famous problem and are there any works related to this problem?

$Note:$ It can be seen that if the factors of $m\in S$ be as much possible as close to each other, then the sum of its factors converges to the minimum.

Answer by Shahrooz for What are the major open problems in design theory nowaday?

2013-01-10T20:10:09Z

These four below problems are interesting and still open conjecture in design theory and its related topics:

$1.$ There exist Ucycles for $k$-subsets of $[n]$, provided $k$ divides $Cr(n-1,k-1)$ and $n$ is sufficiently large.

$2.$ For $n≥6$ even, it is not possible to have a length $\frac{n^2}{2}$ cyclic covering word for the $(n−2)$-subsets of an $n$-set.

$3.$ For each $k≥3$, there exists a constant $c_k$ such that for all $v≥c_k$ and $λ≥1$, the $1$ block-intersection graph of any $BIBD(v,k,λ)$ is Hamiltonian.

$4.$ For each $k≥3$, there exists a constant $c_k$ such that for all $v≥c_k$ and $λ≥1$, the ${1,2}$-block-intersection graph of any $BIBD(v,k,λ)$ is Hamiltonian.

These four conjectures are respectively from:

$1.$ Chung, F., Diaconis, P., Graham, R.: Universal cycles for combinatorial structures. Discrete Math.110, 43–59 (1992)

$2.$ Stevens, B., Buskell, P., Ecimovic, P., Ivanescu, C., Malik, A., Savu, A., Vassilev, T., Verrall, H., Yang, B., Zhao, Z.: Solution of an outstanding conjecture: the non-existence of universal cycles withk=n−2. Discrete Math.258, 193–204 (2002)

$3.$ Jesso, Andrew T.(3-NF); Pike, David A.(3-NF); Shalaby, Nabil(3-NF) Hamilton cycles in restricted block-intersection graphs. (English summary) Des. Codes Cryptogr.61(3), 345–353

$Also,$ I believe that Hadamard conjecture is a nice diamond in the conjectures land.

The cliques of cospectral graphs

2013-01-01T22:54:19Z

There are some facts that can be found by the spectrum of adjacency matrix of graph.For example, the number of edges and vertices, is bipartite or not, is complete multipartite or not and so on. Can we say anything about the clique number of two cospectral graphs?

We can construct the graphs $G_1$ and $G_2$ that they are cospectral and for arbitrary $k\in N$, the difference of clique number of these two graphs be grater than $k$. But, as I know, these graphs are disconnected.

So, my question is in connected case. I mean, suppose $G_1$ and $G_2$ are cospectral and connected. What can we say about their clique numbers?

Thanks for any helpful answer.

Answer by Shahrooz for Difference of the maximum eigenvalue of a graph with the one of one-edge-deleted subgraph

2012-12-17T21:49:10Z

This conjecture is not true in general. For example, let $G$ be a graph that obtained from joining the end vertex of $P_3$, $P_3$ and $P_4$, where it is an star-like tree. This graph has largest eigenvalue equal to $2.02852$. Now join the end vertex of $P_4$ to the end vertex of $P_3$. Therefore we added an edge to the previous graph. The largest eigenvalue of this graph is $2.13578$. Then the difference of this values is $0.10726$. But this graph has $8$ vertices and $1/8=0.125$. It is a counter example.

Also, we can construct a family of star-like tree that does not have this property. Also, I think for any polynomial $f(n)$, we can construct a graph $G$ such that $\lambda(G)-\lambda(G-e)\geq \frac{1}{f(n)}$ is not true.

Decomposition of Matrix to its sub-matrix with constant rank

2012-12-07T19:19:16Z

When we study the structure of simple graphs with a lot of $1$ or $-1$ as its adjacency eigenvalues, the rank of its adjacency matrix is very important. The reason is, in these case, we can study the matrix $A+I$ and $A-I$, where $A$ is the adjacency matrix of graph $G$.

Let $A$ be a symmetric $n\times n$ matrix such that $A+I$ has rank $k$. It is obvious to see that, $A$ has $k$ eigenvalues $-1$. Since $A$ is symmetric, we can write

\begin{equation*} A+I= \begin{bmatrix} A_1& B \newline B^T& A_2 \end{bmatrix} , \end{equation*}

where $A_1$ is a $k\times k$ matrix, $B$ is $k\times (n-k)$ matrix, $B^T$ is the transpose of $B$ and $A_2$ is $(n-k)\times (n-k)$ matrix. It is easy to see that $A_1$ is nonsingular.

My question is:

1) In general, is it true that $A_2=B^TA_1^{-1}B$, and if it is true, how we can prove it? We can see that $rank(A+I)=rank(A_1)$. May be it can help for proof as a strategy.

2) Would you please give me some references for these types of relations in matrices?

For rank$(A_1)=2$ or rank$(A_1)=3$, Professor Doob and Professor Haemers showed that, the structure of $A$ are determined, equivalently, the graphs with $n$ vertices and $n-2$ or $n-3$ eigenvalues $-1$ are determined by their adjacency spectrum. The answer for $n-4$ eigenvalues equal to $-1$ is negative. My another question is:

For which integer $n-k$, where $4\leq k\leq n$, the answer is known? I mean, if the multiplicity of $-1$ for graph $G$ with $n$ vertices be $n-k$, what are the known results about cospectral mate?

Professor Doob and Haemers, gave and example for $n-4$. I found some examples in other cases. I think these examples are important. Am I thinking truly?

I will appreciate any helpful answer and guidance.

Answer by Shahrooz for Does every bipartite graph with 512 edges have an induced subgraph with 256 edges?

2012-11-12T10:55:50Z

You are right Dear domotorp,

Suppose the second largest eigenvalue of bipartite graph $G$ is one, i.e, $\lambda_2=1$. In this case, $G$ belong to the finite type, (there are infinite number of such graphs), bipartite graphs. With some calculation, we can see that your conjecture is true for this type of graphs. Also, we can say more, if we use some other spectral techniques.

The Paper Reference:

Petrovic M., On graphs with exactly one eigenvalue less than -1, J. Combin. Theory Ser. B 52 (1991), 102-112.

Cayley graphs and its subgraphs

2012-01-04T18:54:19Z

I have two questions about Cayley graphs. Any answers will be appreciate.

1) Do we have any Cayley graph that has Petersen graph as its induced subgraph?

2) Suppose $Cay(G,S)$ be a Cayley graph that $G$ is a finite group. Can we characterize any induced subgraphs of $Cay(G,S)$?

Thanks for any answer and guidance.

Battle of the brains; cultural mathematics

2012-07-20T13:09:54Z

Firstly, I apologize if my question is long.

Three years ago, I watched a video with the name Battle of the Brains. It was a wonderful video about challenging some famous peoples to solve some special problems. I learned many new things from this video. Unfortunately, I could not find any similar video, but I interested in the abilities of people to attack a problem.

So, I studied many references about the system of educations in different countries. I found many parameters as like as; teacher education and qualifications, academic standards, teacher effectiveness, lesson plans and modules, teacher characteristics, instructional materials, program effectiveness, program evaluation, culture, history, class activities, educational games, number systems, cognitive ability, foreign influence, and fundamental concepts, are so important in learning mathematics.

Recently, I found the book African Mathematics: From Bones to Computers by Mamokgethi Setati, Abdul Karim Bangura that is very interesting. I think there are some good references as like as this book. My requests are:

Would you please introduce me video files as like as Battle of the Brains?
Would you please introduce textbooks or sites that are about cultural mathematics as like as the book above?

I think there are some references about the research of American mathematicians in Chinese cultural mathematics. I will appreciate, if someone reference these documents.

Answer by Shahrooz for Not especially famous, long-open problems which anyone can understand

2012-06-22T21:50:45Z

I think nobody pointed this problem, if it is repeated, please say me to delete it. This problem killed me for three weeks, when I was a young student in high school. So, I want to recall it again.

$Problem:$ Find all right triangles with rational sides, where the area of these triangles are integer?

I think it is still open problem and if somebody can solve it, I will give 100$ as a small award.

After I searched, I found these two interesting sources. I hope it will be helpful.

1) N.Koblitz, Introduction to elliptic curves and modular forms, volume 97 of Graduate Texts in Mathematics. Springer-Verlag, New York, second edition, 1993.

2) Washington, Lawrence C., Elliptic Curves : Number Theory and Cryptography, CRC Press Series On Discrete Mathematics and Its Applications

Good Surface,Bad Surface-Surface classification

2012-01-09T10:31:06Z

Maybe this question be very simple, but I don't know why it is hard for me. Thanks for any guide and help.

We say a surface $S$ (2-dimensional metric(compact) Riemannian surface) is good (denote by $GS$), if every $2n$, $n\geq1$, points on surface can be separate by some geodesic to two distinct subsets $V_1$ and $V_2$, where $|V_1|=|V_2|=n$. Also, if a surface $S$ is not good, we say it is bad an denote it by $BS$.

For example, it is not difficult to show that plane is a $GS$. Also, a sphere is $GS$.

1) Do we have some $BS$ examples(class of examples)?

2) Can we characterize the $GS$ and $BS$ surfaces?

I can't find any $BS$ examples and also I can't prove that they are $GS$.

For example, is Klein Bottle $GS$ or $BS$?

Is there any related works and questions about this post?

Answer by Shahrooz for Where is number theory used in the rest of mathematics?

2012-03-09T19:10:08Z

What is your idea about a problem in number theory that says:

$\frac{p^q-1}{p-1}$ never divides $\frac{q^p-1}{q-1}$ if $p,q$ are distinct primes.

This is a $\textbf{conjecture}$ and the validity of this conjecture would simplify the proof of solvability of groups of odd order, (W. Fiet, J. G. Thompson, $\textit{Pacific J. Math.}$, 13, no.3 (1963), 775-1029), rendering unnecessary the detailed use of generators and relations.

An other interesting application of number theory is in real world. Many years ago, cables used for communication. A lot of cables must be gathered near to each other for more efficiency. But for blocking the noises of each cable to the other cable, a special arrange of cables needed. For this arrangement and neighboring of cables, scientist used reminder theorem and number theory. I think first time, Bell company's scientists invented it.

Also, I think this relation between group theory, graph theory and number theory is very nice example: Suppose the order of group $G$, $|G|$, is $n=p_1^{k_1}p_2^{k_2}\ldots p_s^{k_s}$. We fix two prime numbers $p_i$ and $p_j$ of divisors of $n$ and define a graph $\Gamma(G)$ as fallow:

The vertices of $\Gamma(G)$ are the elements of group $G$ and two vertices $g_1$ and $g_2$ are adjacent if and only if $o(g_1g_2)=p_ip_j$, where $o$ means the order of element $g_1g_2$ as a group element. These graphs have very nice structures and well defined as $\textit{Prime Graph}$ of group.

Answer by Shahrooz for practical applications of eigenvalues and eigenvectors

2012-02-03T10:14:40Z

I think the book $Spectra$ $of$ $Graphs$$:$ $Theory$ $and$ $Applications$ by Dragos M. Cvetkovic, Michael Doob, Horst Sachs and M. Cvetkovic is very good source for practical applications of eigenvalues and eigenvectors.

In communication theory, coding theory and cryptography, the minimum distance of codes is very important parameter in decoding and also is very important in coding based cryptography (for example McEliece cryptosystem). It is interesting that the second largest eigenvalue of related graph to a code, can determine a good lower-bond for minimum distance of code.

Answer by Shahrooz for Interesting applications of the Pigeon-hole Principle

2012-01-26T09:15:04Z

I think the solutions of these questions are very interesting (by using pigeon-hole principle), first question is easy, but second question is more advanced:

1) For any integer $n$, There are infinite integer numbers with digits only $0$ and $1$ where they are divisible to $n$.

2) For any sequence $s=a_1a_2\cdots a_n$, there is at least one $k$, such that $2^k$ begin with $s$.

Homotopical Combinatorics

2012-01-07T11:08:50Z

I have a question about the situation of homotopical combinatorics. There are many topics about combinatorial homotopy. But, I can't find any topic about homotopical combinatorics. More precisely, are there any definitions for some combinatorial objects as like as Latin Squares, Designs and etc in homotopy theory?

Do we have any examples about the applications of homotopy theory in combinatorics and graph theory? I think there are some generalizations for the definitions of some combinatorial objects in the language of homotopy theory.

Is this true thinking or not? Please guide me, if you have some experiences.

Answer by Shahrooz for Looking for a collection of entry level proofs

2012-01-07T21:47:21Z

I think you have to determine some categories, as like as number theory, combinatorics, geometry and etc. But I think this book is so interesting:

"Ingenuity in Mathematics" by Ross Hansberger

Graphical representation of chromatic polynomial

2012-01-01T19:03:00Z

Suppose $c(G,u)$ is chromatic polynomial of connected simple graph $G$. We know that $|c(G,-1)|$, as Stanley proved, is the total number of directed graph on $G$, without any cycle. Also, we know some other graphical representations of the value of $c(G,u)$.

1) Do we have any graphical representation for $|c(G,2)|$?

2) Do we have any graphical representation for the multiplicity of $2$ as a root of $c(G,u)$?

I found some graphical representation for these values, but I didn't prove them yet.

Thanks for any helpful answer and good references.

Answer by Shahrooz for How might M.C. Escher have designed his patterns?

2012-01-02T19:41:48Z

When I was in high-school, my teacher suggested a very interesting method for generating some interesting Escher's like pictures. I think it is useful for you.

Get a mirror(or something like mirror) and construct some geometrical shape with this mirror, for example an cylinder, that the inner surface of this shape is mirror. Now, collect some isomorphic shape, for example shell, flower, or simply some triangles. If we put these objects inside the cylinder, we find very beautiful Escher-like shape on the mirror. With some simple method in photography, we can obtain the picture that is inside the cylinder. We can change the shape of mirror and create some elegant symmetry.

I didn't see this method anywhere. I hope it will be useful for you.

To memory of Escher.

Answer by Shahrooz for Generalizing Euclid's proof of the infinity of primes

2012-01-02T19:20:40Z

Dear Currie

The below problem is still open:

Do we have infinite prime number of the form $2p+1$, where $p$ is prime?

One of interesting way to examine this problem is %Sandram$ table. For further information about Sandram table, you can see the book

" Ingenuity in Mathematics" by Ross Hansberger

Also, with some calculation and using the Jacobi symbol, you will find this problem is equivalent to this problem:

The polynomial $n^2+n-1$ generate infinite prime number, that it is open problem. You can find some further information about this question in the Richard Guy's book with name:

" Open problem in number theory".

So I think your problem is a kind of open problem.

learning sources about Ihara Coefficient

2011-12-30T22:42:05Z

Do we have any good sources(lecture notes or books) for learning about $Ihara$ Coefficient?

Is there any relation between $Ihara$ Coefficient and the eigenvalues of graphs?

Thanks for any help.

Estimation of DS graph growth

2011-12-25T22:49:16Z

We know that $DS$ graphs are such connected graphs that determinable by their adjacency spectrum.

Suppose $DS(n)$ and $G(n)$ show the number of $DS$ graphs and all graphs with $n$ vertices,respectively.

$1)$ Do we have any good approximation for $DS(n)$(even if $n$ be sufficiently large)?

$2)$ what is the behavior of $‎\alpha$, if we have:

‎ $lim (DS(n)‎‎/ (G(n)-DS(n))^\alpha=c‎\neq‎0)$

$n ‎\rightarrow‎‎ ‎\infty‎$

Is there any new survey about DS graphs, after 2010?

Non-isomorphic graphs with the same numbers of closed walks

2011-12-22T13:53:35Z

Can somebody help me to construct two family of finite simple connected graph $G_i$ and $H_i$, $i=1, 2, \cdots,n$ ($n$ possibly large), such that:

$1)$ $G_i‎\ncong H_i$ for $i=1, 2, \cdots, n$

$2)$ $|V(G_i)|=|V(H_i)|, |E(G_i)|=|E(H_i)|$

$3)$ If $C_k(G)$ denotes the number of closed walk of length $k$ in graph $G$, we have:

$C_k(G_i)=C_k(H_i)$ for $i=1, 2, \cdots, n$

$4)$ Preferably, I need these graphs be $a)$minimal and $b)$highly irregular(or has one of these two conditions $(a)$ or $(b)$).

$Definition 1:$ A graph $G$ is Highly irregular, if every vertex $v$ of $G$ is adjacent only to vertices with distinct degrees.

$Definition 2:$ The sequence of graphs $G_i$,$i=1,2,\cdots,n$, is minimal, if the number of vertices of every $G_i$ is minimum.

For example, two trees $T_1$ and $T_2$ with degree sequences $4,4,1,1,1,1,1,1$ and $5,2,2,1,1,1,1,1$ respectively, are minimal, because they are minimum vertices co-spectral trees.

I will appreciate any help and guidance.

Operation on Isospectral graphs

2011-12-18T19:15:08Z

Suppose $G$ and $H$ are two isospectral connected graphs. Can we say anything about isospectrality of graphs that obtain by binary operation between $G$ and $H$? For example,in special case, is $G‎\otimes‎G$(Kronecker product) isospectral? which binary operations between $G$ and $H$, preserve the isospectrality?

Counting Special Graphs

2011-12-16T15:25:01Z

Do we have any formula for counting the number of graphs with $n$ vertices, that has exactly $k$ vertices with degree $d$ and the other vertices have different and disjoint degrees? (Different and disjoint are the same, $d_1$ is different or disjoint rather than $d_2$, iff $d_1\neq‎ d_2$.)

For example, for $n=3, k=2, d=1$, we only have one graph($P_3$) with this property. Also, for $n=4, k=2, d=2$, we have the only graph with degree sequence $1, 2, 2, 3$.

Comment by Shahrooz

2013-04-28T19:20:29Z

Dear Prof. Abdollahi, after some attempts, I could not find suitable $A$.

Comment by Shahrooz

2013-04-27T20:31:14Z

Dear Prof. Abdollahi, I am thinking about $Q_8 \times G$, where $G$ is a suitable infinite abelian poly-cyclic group. Did you examined such groups?

Comment by Shahrooz

2013-03-29T09:26:03Z

Dear Eremenko, your answer was interesting for me, since I did not know that Mandelbrot did not prove new theorem in fractal geometry. I think general relativity and Non-Euclidean geometry has same story. Einstein just found the relation between his theory and a suitable geometry.

Comment by Shahrooz

2013-03-18T18:55:36Z

Dear geoffreyexoo, thanks for your explanation. For me, the number of examples that you found is sufficient to accept my wrong imagination. But, these number of graphs among all 4-regular graphs with 32 vertices is very small.

Comment by Shahrooz

2013-03-17T20:55:50Z

Very nice, dear geoffreyexoo, what was your strategy for finding this graph? I found some 4-regular graphs with diameter 4. Also by some papers that BOLLOBAS and his coworkers wrote, I think there are a little number of such graph that you found one of them.

Comment by Shahrooz

2013-03-17T12:09:10Z

By this address: mathworld.wolfram.com/QuarticGraph.html and a probabilistic program that I wrote in Maple (and with 20 min run, that I know it is very small time), I think there is not such a graph. It is interesting for me if such a graph exist. Also, I think Dear McKay with Naughty software, can help you more than me. Also, it is obvious that, such a graph (if it exist) is not strongly regular.

Comment by Shahrooz

2013-03-13T19:38:59Z

Dear Valette, I did not aware about these groups of graphs. Thank you very much because of the links. Your first paper is "666.02" Kb that we discussed this number with dear Meyerowitz. So strange!!

Comment by Shahrooz

2013-03-13T19:28:31Z

Dear Hopkins, this group is interesting. Thanks for your answer. Dear Meyerowitz, It is obvious that I did not used my imagination for asking this question. I used the Google and some famous paper databases, and after that I asked this question. But, I am agree with you that my imagination is a limit. About, 666, I know it belongs to our dear common friend "Satan". But it is very strange that, how you know my mobile number ends with this three digits. Finally, thanks for your good comments.

Comment by Shahrooz

2013-02-08T10:24:08Z

In general no, but these references maybe good for further study: 1. "THE NORMALIZED LAPLACIAN MATRIX AND GENERAL RANDIC INDEX OF GRAPHS", a thesis by "Michael Scott Cavers" 2. "Generalizing some results to the normalized Laplacian" by "Steve Butler"

Comment by Shahrooz

2013-02-08T10:09:43Z

Oops, you are absolutely right.

Comment by Shahrooz

2013-02-07T22:02:50Z

Dear Aaron, did you assume that any $m$ adjacent vertices have exactly one common vertex as a neighbor? In the question, this assumption does not exist. Am I thinking truly?

Comment by Shahrooz

2013-02-07T14:27:24Z

Let $A_m$ be the set of all graphs with $m$ vertices and that they have not dominating vertex. So, why the cone over any subset of $A_m$ is not an answer?

Comment by Shahrooz

2013-02-07T14:19:43Z

But for your problem, the graph has a dominating vertex and also the graph is $P_4$ free.

Comment by Shahrooz

2013-02-07T14:12:00Z

I think if you want to generalize the friendship theorem, you have to see one of important parameter in its definition. In the definition of friendship graph, any two adjacent vertices have exactly one common neighbor. By your definition, you deleted this condition and it is not the generalization of friendship graph.

Comment by Shahrooz

2013-01-21T15:59:56Z

Dear Kohl, thanks for your note.