Hamiltonian and long paths in bipartite graphs with connectivity

Let G be a graph, $\nu (G)$ the order of G, $\kappa (G)$ the connectivity of G and k a positive integer such that $k\le (\nu (G)?2)/2$. Then G is said to be k-extendable if it has a matching of size k and every matching of size k extends to a perfect matching of G. A Hamiltonian path of a graph G is a spanning path of G. A bipartite graph G with vertex sets $V_1$ and $V_2$ is defined to be Hamiltonian-laceable if such that $|V_1|=|V_2|$ and for every pair of vertices $p\in V_1$ and $q\in V_2$, there exists a Hamiltonian path in G with endpoints p and q, or $|V_1|=|V_2|+1$ and for every pair of vertices $p,q\in V_1,p\ne q$, there exists a Hamiltonian path in G with endpoints p and q. Let G be a bipartite graph with bipartition $(X,Y)$. Define $bn(G)$ to be a maximum integer such that $0\le bn(G)<min\{|X|,|Y|\}$ and (1) for each non-empty subset S of X, if $|S|\le |X|?bn(G)$, then $|N(S)|\ge |S|+bn(G)$, and if $|X|?bn(G)<|S|\le |X|$, then $N(S)=Y$; and (2) for each non-empty subset S of Y, if $|S|\le |Y|?bn(G)$, then $|N(S)|\ge |S|+bn(G)$, and if $|Y|?bn(G)<|S|\le |Y|$, then $N(S)=X$; and (3) $bn(G)=0$ if there is no non-negative integer satisfying (1) and (2).Let G be a bipartite graph with bipartition $(X,Y)$ such that $|X|=|Y|$ and $bn(G)>0$. In this paper, we show that if $\nu (G)\le 2\kappa (G)+4bn(G)?4$, then G is Hamiltonian-laceable; or if $\nu (G)>6bn(G)?2$, then for every pair of vertices $x\in X$ and $y\in Y$, there is an $(x,y)$-path P in G with $|V(P)|\ge 6bn(G)?2$. We show some of its corollaries in k-extendable, bipartite graphs and a conjecture in k-extendable graphs.     

The maximum multiplicity of the largest k-th eigenvalue in a matrix whose graph is acyclic or unicyclic

Given a graph $G$ we are interested in studying the symmetric matrices associated to $G$ with a fixed number of negative eigenvalues. For this class of matrices we focus on the maximum possible nullity. For trees this parameter has already been studied and plenty of applications are known. In this work we derive a formula for the maximum nullity and completely describe its behavior as a function of the number of negative eigenvalues. In addition, we also carefully describe the matrices associated with trees that attain this maximum nullity. The analysis is then extended to the more general class of unicyclic graphs. Further our work is applied to re-describing all possible partial inertias associated with trees, and is employed to study an instance of the inverse eigenvalue problem for certain trees.     

Linearly χ-bounding (P6, C4)-free graphs*

Given two graphs and , a graph is -free if it contains no induced subgraph isomorphic to or . Let and be the path on vertices and the cycle on vertices, respectively. In this paper we show that for any -free graph it holds that , where and are the chromatic number and clique number of , respectively. Our bound is attained by several graphs, for instance, the 5-cycle, the Petersen graph, the Petersen graph with an additional universal vertex, and all -critical -free graphs other than (see Hell and Huang [Discrete Appl. Math. 216 (2017), pp. 211–232]). The new result unifies previously known results on the existence of linear -binding functions for several graph classes. Our proof is based on a novel structure theorem on -free graphs that do not contain clique cutsets. Using this structure theorem we also design a polynomial time -approximation algorithm for coloring -free graphs. Our algorithm computes a coloring with colors for any -free graph in time.     

Signed graphs and the freeness of the Weyl subarrangements of type Bℓ

A Weyl arrangement is the hyperplane arrangement defined by a root system. Saito proved that every Weyl arrangement is free. The Weyl subarrangements of type $A_{\ell }$ are represented by simple graphs. Stanley gave a characterization of freeness for this type of arrangements in terms of their graph. In addition, the Weyl subarrangements of type $B_{\ell }$ can be represented by signed graphs. A characterization of freeness for them is not known. However, characterizations of freeness for a few restricted classes are known. For instance, Edelman and Reiner characterized the freeness of the arrangements between type $A_{\ell -1}$ and type $B_{\ell }$. In this paper, we give a characterization of the freeness and supersolvability of the Weyl subarrangements of type $B_{\ell }$ under certain assumption.     

On signed graphs with just two distinct adjacency eigenvalues

In this paper, all simple connected signed graphs with maximum degree at most 4 and with just two distinct adjacency eigenvalues are completely characterized, there exists an infinite family of 4-regular signed graphs with just two distinct adjacency eigenvalues.     

An infinite family of subcubic graphs with unbounded packing chromatic number

Recently, Balogh et al. (2018) answered in negative the question that was posed in several earlier papers whether the packing chromatic number is bounded in the class of graphs with maximum degree 3. In this note, we present an explicit infinite family of subcubic graphs with unbounded packing chromatic number.