On Hallian digraphs, permanents and transversals
In this paper, we improve the result by Harper on the lower bound of the bandwidth of connected graphs. In addition, we prove that considerating the interior boundary and the exterior boundary when estimating the bandwidth of connected graphs gives the same results.
The composition graph of a family of n+1 disjoint graphs is the graph H obtained by substituting the n vertices of H₀ respectively by the graphs H₁,H₂,...,Hₙ. If H has some hereditary property P, then necessarily all its factors enjoy the same property. For some sort of graphs it is sufficient that all factors have a certain common P to endow H with this P. For instance, it is known that the composition graph of a family of perfect graphs is also a perfect graph (B. Bollobas, 1978), and the...