The size Ramsey number of short subdivisions of bounded degree graphs

For graphs G and F, write if any coloring of the edges of G with colors yields a monochromatic copy of the graph F. Suppose is obtained from a graph S with s vertices and maximum degree d by subdividing its edges h times (that is, by replacing the edges of S by paths of length h + 1). We prove that there exists a graph G with no more than edges for which holds, provided that . We also extend this result to the case in which Q is a graph with maximum degree d on q vertices with the property that every pair of vertices of degree greater than 2 are distance at least h + 1 apart. This complements work of Pak regarding the size Ramsey number of “long subdivisions” of bounded degree graphs.     

Asymmetry and structural information in preferential attachment graphs

Graph symmetries intervene in diverse applications, from enumeration, to graph structure compression, to the discovery of graph dynamics (e.g., node arrival order inference). Whereas Erd?s‐Rényi graphs are typically asymmetric, real networks are highly symmetric. So a natural question is whether preferential attachment graphs, where in each step a new node with m edges is added, exhibit any symmetry. In recent work it was proved that preferential attachment graphs are symmetric for m = 1, and there is some nonnegligible probability of symmetry for m = 2. It was conjectured that these graphs are asymmetric when m ≥ 3. We settle this conjecture in the affirmative, then use it to estimate the structural entropy of the model. To do this, we also give bounds on the number of ways that the given graph structure could have arisen by preferential attachment. These results have further implications for information theoretic problems of interest on preferential attachment graphs.     

Uniform random colored complexes

We present here random distributions on (D + 1)‐edge‐colored, bipartite graphs with a fixed number of vertices 2p. These graphs encode D‐dimensional orientable colored complexes. We investigate the behavior of those graphs as p→∞. The techniques involved in this study also yield a Central Limit Theorem for the genus of a uniform map of order p, as p→∞.     

二部图形式的Erd\H{O}s-S\'{o}s猜想

二部图形式的Erd\H{O}s-S\''{o}s猜想     

The impact of loops on the game of cops and robbers on graphs

In the game of cops and robbers on graphs, the cops and the robber are allowed to pass their turn if they are located on a looped vertex. This paper explores the effect of loops on the cop number and the capture time. We provide examples of graphs where the cop number almost doubles when the loops are removed, graphs where the cop number decreases when the loops are removed, graphs where the capture time is quadratic in the number of vertices and copwin graphs where the cop needs to move away from the robber in optimal play.     

On s-hamiltonian line graphs of claw-free graphs

For an integer $s\ge 0$, a graph $G$ is $s$-hamiltonian if for any vertex subset $S?V\left(G\right)$ with $\left|S\right|\le s$, $G?S$ is hamiltonian, and $G$ is $s$-hamiltonian connected if for any vertex subset $S?V\left(G\right)$ with $\left|S\right|\le s$, $G?S$ is hamiltonian connected. Thomassen in 1984 conjectured that every 4-connected line graph is hamiltonian (see Thomassen, 1986), and Ku?zel and Xiong in 2004 conjectured that every 4-connected line graph is hamiltonian connected (see Ryjá?ek and Vrána, 2011). In Broersma and Veldman (1987), Broersma and Veldman raised the characterization problem of $s$-hamiltonian line graphs. In Lai and Shao (2013), it is conjectured that for $s\ge 2$, a line graph $L\left(G\right)$ is $s$-hamiltonian if and only if $L\left(G\right)$ is $(s+2)$-connected. In this paper we prove the following.(i) For an integer $s\ge 2$, the line graph $L\left(G\right)$ of a claw-free graph $G$ is $s$-hamiltonian if and only if $L\left(G\right)$ is $(s+2)$-connected.(ii) The line graph $L\left(G\right)$ of a claw-free graph $G$ is 1-hamiltonian connected if and only if $L\left(G\right)$ is 4-connected.     

Vertex partitions of (C3,C4,C6)-free planar graphs

A graph is $(k_1,k_2)$-colorable if it admits a vertex partition into a graph with maximum degree at most $k_1$ and a graph with maximum degree at most $k_2$. We show that every $(C_3,C_4,C_6)$-free planar graph is $(0,6)$-colorable. We also show that deciding whether a $(C_3,C_4,C_6)$-free planar graph is $(0,3)$-colorable is NP-complete.     

A new arithmetic criterion for graphs being determined by their generalized Q-spectrum

“Which graphs are determined by their spectrum (DS for short)?” is a fundamental question in spectral graph theory. It is generally very hard to show a given graph to be DS and few results about DS graphs are known in literature. In this paper, we consider the above problem in the context of the generalized $Q$-spectrum. A graph $G$ is said to be determined by the generalized $Q$-spectrum (DGQS for short) if, for any graph $H$, $H$ and $G$ have the same $Q$-spectrum and so do their complements imply that $H$ is isomorphic to $G$. We give a simple arithmetic condition for a graph being DGQS. More precisely, let $G$ be a graph with adjacency matrix $A$ and degree diagonal matrix $D$. Let $Q=A+D$ be the signless Laplacian matrix of $G$, and $W_Q\left(G\right)=[e,Qe,\dots ,Q^{n-1}e]$ ($e$ is the all-ones vector) be the $Q$-walk matrix. We show that if $\frac{det{W}_Q\left(G\right)}{2^{\lfloor \frac{3n-2}{2}\rfloor }}$ (which is always an integer) is odd and square-free, then $G$ is DGQS.