Let $K_m-H$ be the graph obtained from $K_m$ by removing the edges set $E(H)$ of $H$ where $H$ is a subgraph of $K_m$. In this paper, we characterize the potentially $K_5-P_4$ and $K_5-Y_4$-graphic sequences where $Y_4$ is a tree on 5 vertices and 3 leaves.
We use graph-algebraic results proved in [8] and some results of the graph theory to characterize all pairs ⟨L1, L2⟩ of lattices for which there is a finite partial unary algebra such that its weak and strong subalgebra lattices are isomorphic to L1 and L2, respectively. Next, we describe other pairs of subalgebra lattices (weak and relative, etc.) of a finite unary algebra. Finally, necessary and sufficient conditions are found for quadruples ⟨L1, L2, L3, L4⟩ of lattices for which there is a finite unary algebra having its weak, relative, strong subalgebra and initial segment lattices isomorphic to L1, L2, L3, L4, respectively.
In this note we show that 1-skeletons and 2-skeletons of n-pseudomanifolds with full boundary are (n+ 1)-connected graphs and n-connected 2-complexes, respectively. This generalizes previous results due to Barnette and Woon.
The set of all non-increasing nonnegative integer sequences $\pi =$ ($d(v_1 ),d(v_2 ), \dots , d(v_n )$) is denoted by ${\rm NS}_n$. A sequence $\pi \in {\rm NS}_n$ is said to be graphic if it is the degree sequence of a simple graph $G$ on $n$ vertices, and such a graph $G$ is called a realization of $\pi $. The set of all graphic sequences in ${\rm NS}_n$ is denoted by ${\rm GS}_n$. A graphical sequence $\pi $ is potentially $H$-graphical if there is a realization of $\pi $ containing $H$ as a subgraph, while $\pi $ is forcibly $H$-graphical if every realization of $\pi $ contains $H$ as a subgraph. Let $K_k$ denote a complete graph on $k$ vertices. Let $K_m-H$ be the graph obtained from $K_m$ by removing the edges set $E(H)$ of the graph $H$ ($H$ is a subgraph of $K_m$). This paper summarizes briefly some recent results on potentially $K_m-G$-graphic sequences and give a useful classification for determining $\sigma (H,n)$.
This paper introduces a method how to transform one regular grammar to the second one. The transformation is based on regular grammar distance computation. Regular grammars are equivalent to finite states machines and they are represented by oriented graphs or by transition matrices, respectively. Thus, the regular grammar distance is defined analogously to the distance between two graphs. The distance is measured as the minimal count of elementary operations over the grammar which transform the first grammar to the second one. The distance is computed by searching an optimal mapping of non-terminal symbols of both grammars. The computation itself is done by the genetic algorithm because the exhaustive evaluation of mapping leads to combinatorial explosion. Transformation steps are derived from differences in matrices. Differences are identified during the computation of the distance.
ct. Guy and Harary (1967) have shown that, for k > 3, the graph P[2k, k] is homeomorphic to the Möbius ladder M2k, so that its crossing number is one; it is well known that P[2k, 2] is planar. Exoo, Harary and Kabell (1981) have shown hat the crossing number of P[2k + 1, 2] is three, for k ≥ 2. Fiorini (1986) and Richter and Salazar (2002) have shown that P[9, 3] has crossing number two and that P[3k, 3] has crossing number k, provided k ≥ 4. We extend this result by showing that P[3k, k] also has crossing number k for all k ≥ 4.
The Laplacian spectral radius of a graph is the largest eigenvalue of the associated Laplacian matrix. In this paper, we improve Shi's upper bound for the Laplacian spectral radius of irregular graphs and present some new bounds for the Laplacian spectral radius of some classes of graphs.
Suppose that A is a real symmetric matrix of order n. Denote by m_{A}(0) the nullity of A. For a nonempty subset α of {1, 2,..., n}, let A(α) be the principal submatrix of A obtained from A by deleting the rows and columns indexed by α. When m_{A(\alpha )}(0) = m_{A}(0)+|α|, we call α a P-set of A. It is known that every P-set of A contains at most \left \lfloor n/2 \right \rfloorelements. The graphs of even order for which one can find a matrix attaining this bound are now completely characterized. However, the odd case turned out to be more difficult to tackle. As a first step to the full characterization of these graphs of odd order, we establish some conditions for such graphs G under which there is a real symmetric matrix A whose graph is G and contains a P-set of size (n − 1)/2., Zhibin Du, Carlos M. da Fonseca., and Obsahuje seznam literatury
In this paper, by a travel groupoid is meant an ordered pair $(V, *)$ such that $V$ is a nonempty set and $*$ is a binary operation on $V$ satisfying the following two conditions for all $u, v \in V$: \[ (u * v) * u = u; \text{ if }(u * v ) * v = u, \text{ then } u = v. \] Let $(V, *)$ be a travel groupoid. It is easy to show that if $x, y \in V$, then $x * y = y$ if and only if $y * x = x$. We say that $(V, *)$ is on a (finite or infinite) graph $G$ if $V(G) = V$ and \[ E(G) = \lbrace \lbrace u, v\rbrace \: u, v \in V \text{ and } u \ne u * v = v\rbrace . \] Clearly, every travel groupoid is on exactly one graph. In this paper, some properties of travel groupoids on graphs are studied.