Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCharacterizing graphs of maximum matching width at most 2
63
0
0.0
(
0
)
Added by
Jisu Jeong
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The maximum matching width is a width-parameter that is defined on a branch-decomposition over the vertex set of a graph. The size of a maximum matching in the bipartite graph is used as a cut-function. In this paper, we characterize the graphs of maximum matching width at most 2 using the minor obstruction set. Also, we compute the exact value of the maximum matching width of a grid.
rate research
Read More
A signed graph is a pair $(G,Sigma)$, where $G=(V,E)$ is a graph (in which parallel edges are permitted, but loops are not) with $V={1,ldots,n}$ and $Sigmasubseteq E$. The edges in $Sigma$ are called odd and the other edges of $E$ even. By $S(G,Sigma)$ we denote the set of all symmetric $ntimes n$ matrices $A=[a_{i,j}]$ with $a_{i,j}<0$ if $i$ and $j$ are adjacent and connected by only even edges, $a_{i,j}>0$ if $i$ and $j$ are adjacent and connected by only odd edges, $a_{i,j}in mathbb{R}$ if $i$ and $j$ are connected by both even and odd edges, $a_{i,j}=0$ if $i ot=j$ and $i$ and $j$ are non-adjacent, and $a_{i,i} in mathbb{R}$ for all vertices $i$. The parameters $M(G,Sigma)$ and $xi(G,Sigma)$ of a signed graph $(G,Sigma)$ are the largest nullity of any matrix $Ain S(G,Sigma)$ and the largest nullity of any matrix $Ain S(G,Sigma)$ that has the Strong Arnold Hypothesis, respectively. In a previous paper, we gave a characterization of signed graphs $(G,Sigma)$ with $M(G,Sigma)leq 1$ and of signed graphs with $xi(G,Sigma)leq 1$. In this paper, we characterize the $2$-connected signed graphs $(G,Sigma)$ with $M(G,Sigma)leq 2$ and the $2$-connected signed graphs $(G,Sigma)$ with $xi(G,Sigma)leq 2$.
A graph is called $2K_2$-free if it does not contain two independent edges as an induced subgraph. Mou and Pasechnik conjectured that every $frac{3}{2}$-tough $2K_2$-free graph with at least three vertices has a spanning trail with maximum degree at most $4$. In this paper, we confirm this conjecture. We also provide examples for all $t < frac{5}{4}$ of $t$-tough graphs that do not have a spanning trail with maximum degree at most $4$.
A classic theorem by Steinitz states that a graph G is realizable by a convex polyhedron if and only if G is 3-connected planar. Zonohedra are an important subclass of convex polyhedra having the property that the faces of a zonohedron are parallelograms and are in parallel pairs. In this paper we give characterization of graphs of zonohedra. We also give a linear time algorithm to recognize such a graph. In our quest for finding the algorithm, we prove that in a zonohedron P both the number of zones and the number of faces in each zone is O(square root{n}), where n is the number of vertices of P.
If the Laplacian matrix of a graph has a full set of orthogonal eigenvectors with entries $pm1$, then the matrix formed by taking the columns as the eigenvectors is a Hadamard matrix and the graph is said to be Hadamard diagonalizable. In this article, we prove that if $n=8k+4$ the only possible Hadamard diagonalizable graphs are $K_n$, $K_{n/2,n/2}$, $2K_{n/2}$, and $nK_1$, and we develop an efficient computation for determining all graphs diagonalized by a given Hadamard matrix of any order. Using these two tools, we determine and present all Hadamard diagonalizable graphs up to order 36. Note that it is not even known how many Hadamard matrices there are of order 36.
Let $G$ be an $n$-vertex graph with adjacency matrix $A$, and $W=[e,Ae,ldots,A^{n-1}e]$ be the walk matrix of $G$, where $e$ is the all-one vector. In Wang [J. Combin. Theory, Ser. B, 122 (2017): 438-451], the author showed that any graph $G$ is uniquely determined by its generalized spectrum (DGS) whenever $2^{-lfloor n/2 rfloor}det W$ is odd and square-free. In this paper, we introduce a large family of graphs $mathcal{F}_n={$ $n$-vertex graphs $Gcolon, 2^{-lfloor n/2 rfloor}det W =p^2b$ and rank$W=n-1$ over $mathbb{Z}/pmathbb{Z}},$ where $b$ is odd and square-free, $p$ is an odd prime and $p mid b$. We prove that any graph in $mathcal{F}_n$ either is DGS or has exactly one generalized cospectral mate up to isomorphism. Moreover, we show that the problem of finding the generalized cospectral mate for a graph in $mathcal{F}_n$ is equivalent to that of generating an appropriate rational orthogonal matrix from a given integral vector. This equivalence essentially depends on an amazing property of graphs in terms of generalized spectra, which states that any symmetric integral matrix generalized cospectral with the adjacency matrix of some graph must be an adjacency matrix. Based on this equivalence, we develop an efficient algorithm to decide whether a given graph in $mathcal{F}_n$ is DGS and further to find the unique generalized cospectral mate when it is not. We give some experimental results on graphs with at most 20 vertices, which suggest that $mathcal{F}_n$ may have a positive density (nearly $3%$) and possibly almost all graphs in $mathcal{F}_n$ are DGS as $nrightarrow infty$. This gives a supporting evidence for Haemers conjecture that almost all graphs are determined by their spectra.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
