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.     

Finding any given 2‐factor in sparse pseudorandom graphs efficiently

Given an $n$‐vertex pseudorandom graph $G$ and an $n$‐vertex graph $H$ with maximum degree at most two, we wish to find a copy of $H$ in $G$, that is, an embedding $\phi :V\left(H\right)\to V\left(G\right)$ so that $\phi \left(u\right)\phi \left(v\right)\in E\left(G\right)$ for all $uv\in E\left(H\right)$. Particular instances of this problem include finding a triangle‐factor and finding a Hamilton cycle in $G$. Here, we provide a deterministic polynomial time algorithm that finds a given $H$ in any suitably pseudorandom graph $G$. The pseudorandom graphs we consider are $\left(p,\lambda \right)$‐bijumbled graphs of minimum degree which is a constant proportion of the average degree, that is, $\mathrm{\Omega }\left(pn\right)$. A $\left(p,\lambda \right)$‐bijumbled graph is characterised through the discrepancy property: $|e\left(A,B\right)?p|A||B||<\lambda \sqrt{|A||B|}$ for any two sets of vertices $A$ and $B$. Our condition $\lambda =O(p^{2}n/\log n)$ on bijumbledness is within a log factor from being tight and provides a positive answer to a recent question of Nenadov. We combine novel variants of the absorption‐reservoir method, a powerful tool from extremal graph theory and random graphs. Our approach builds on our previous work, incorporating the work of Nenadov, together with additional ideas and simplifications.     

Monochromatic k-edge-connection colorings of graphs

A path in an edge-colored graph $G$ is called monochromatic if any two edges on the path have the same color. For $k\ge 2$, an edge-colored graph $G$ is said to be monochromatic $k$-edge-connected if every two distinct vertices of $G$ are connected by at least $k$ edge-disjoint monochromatic paths, and $G$ is said to be uniformly monochromatic $k$-edge-connected if every two distinct vertices are connected by at least $k$ edge-disjoint monochromatic paths such that all edges of these $k$ paths are colored with a same color. We use $m{c}_k\left(G\right)$ and $um{c}_k\left(G\right)$ to denote the maximum number of colors that ensures $G$ to be monochromatic $k$-edge-connected and, respectively, $G$ to be uniformly monochromatic $k$-edge-connected. In this paper, we first conjecture that for any $k$-edge-connected graph $G$, $m{c}_k\left(G\right)=e\left(G\right)-e\left(H\right)+\lfloor \frac{k}{2}\rfloor$, where $H$ is a minimum $k$-edge-connected spanning subgraph of $G$. We verify the conjecture for $k=2$. We also prove the conjecture for $G=K_{k+1}$ and $G=K_{k,n}$ with $n\ge k\ge 3$. When $G$ is a minimal $k$-edge-connected graph, we give an upper bound of $m{c}_k\left(G\right)$, i.e., $m{c}_k\left(G\right)\le k-1$. For the uniformly monochromatic $k$-edge-connectivity, we prove that for all $k$, $um{c}_k\left(G\right)=e\left(G\right)-e\left(H\right)+1$, where $H$ is a minimum $k$-edge-connected spanning subgraph of $G$.     

Characterization and linear-time detection of minimal obstructions to concave-round graphs and the circular-ones property

A graph is concave-round if its vertices can be circularly enumerated so that the closed neighborhood of each vertex is an interval in the enumeration. In this study, we give a minimal forbidden induced subgraph characterization for the class of concave-round graphs, solving a problem posed by Bang-Jensen, Huang, and Yeo [SIAM J. Discrete Math., 13 (2000), pp. 179–193]. In addition, we show that it is possible to find one such forbidden induced subgraph in linear time in any given graph that is not concave-round. As part of the analysis, we obtain characterizations by minimal forbidden submatrices for the circular-ones property for rows and for the circular-ones property for rows and columns and show that, also for both variants of the property, one of the corresponding forbidden submatrices can be found (if present) in any given matrix in linear time. We make some final remarks regarding connections to some classes of circular-arc graphs.     

The 4D Klein-Gordon, Dirac and Quantization Equations from 5D Null Paths

Results from 5D induced-matter and membrane theory with null paths are extended to show that a particle obeys the 4D Klein-Gordon equation but with a variable mass. The Dirac equation also follows, but raises concerns about 4D quantization in the two natural 5D gauges, and reopens the question of a Regge-like trajectory for the spin angular momenta and squared masses of gravitationally-dominated systems.