Search

In this paper, we first introduce a weighted derivation on algebras over an operad $\cal P$, and prove that for the free $\cal P$-algebra, its weighted derivation is determined by the restriction on the generators. As applications, we propose the concept of weighted differential ($q$-tri)dendriform algebras and study some basic properties of them. Then Novikov-(tri)dendriform algebras are initiated, which can be induced from differential ($q$-tri) dendriform of weight zero. Finally, the corresponding free objects are constructed, in both the commutative and noncommutative contexts., Comment: 26 pages. arXiv admin note: substantial text overlap with arXiv:2305.19609

We give an affirmative answer to the open question posed in [34]: are the operated Lie polynomial identities corresponding to new operators on associative algebras in [7] Grobner-Shirshov, respectively?, Comment: 18 pages

Let $G$ be a graph, and let $A(G)$ be the adjacency matrix of $G$. The permanental polynomial of $G$ is defined as $\pi(G,x)=\mathrm{per}(xI-A(G))$. The permanental sum of $G$ can be defined as the sum of absolute value of coefficients of $\pi(G,x)$. Computing the permanental sum is $\#$P-complete. Any a bicyclic graph can be generated from three types of induced subgraphs. In this paper, we determine the upper bound of permanental sums of bicyclic graphs generated from each a type of induced subgraph. And we also determine the second maximal permanental sum of all bicyclic graphs.

Counting maximum matchings in a graph is of great interest in statistical mechanics, solid-state chemistry, theoretical computer science, mathematics, among other disciplines. However, it is a challengeable problem to explicitly determine the number of maximum matchings of general graphs. In this paper, using Gallai-Edmonds structure theorem, we derive a computing formula for the number of maximum matching in a graph. According to the formula, we obtain an algorithm to enumerate maximum matchings of a graph. In particular, The formula implies that computing the number of maximum matchings of a graph is converted to compute the number of perfect matchings of some induced subgraphs of the graph. As an application, we calculate the number of maximum matchings of opt trees. The result extends a conclusion obtained by Heuberger and Wagner[C. Heuberger, S. Wagner, The number of maximum matchings in a tree, Discrete Math. 311 (2011) 2512--2542].

In the present paper, we propose the concepts of weighted differential ($q$-tri)dendriform algebras and give some basic properties of them. The corresponding free objects are constructed, in both the commutative and noncommutative contexts., Comment: This paper is just the old version of the arXiv:2406.12871. Sorry I forget I have uploaded it before. So it would be great to turn arXiv:2305.19609 to version 1 of the newest arXiv:2406.12871

Let $G$ be a graph with $n$ vertices, and let $L(G)$ and $Q(G)$ be the Laplacian matrix and signless Laplacian matrix of $G$, respectively. The polynomial $\pi(L(G);x)={\rm per}(xI-L(G))$ (resp. $\pi(Q(G);x)={\rm per}(xI-Q(G))$) is called {\em Laplacian permanental polynomial} (resp. {\em signless Laplacian permanental polynomial}) of $G$. In this paper, we show that two classes of bicyclic graphs are determined by their (signless) Laplacian permanental polynomials.

The connectivity of a graph is an important parameter to measure its reliability. Structure and substructure connectivity, component connectivity and $k$-restricted connectivity are well-known generalizations of the concept of connectivity, which have been extensively studied from the combinatorial point of view. Very little result is known about their complexity other than the recently obtained computational complexity of $k$-restricted edge-connectivity. In this paper, we zero in on characterizing the complexity of structure and substructure connectivity, component connectivity and $k$-restricted connectivity of graphs, showing that they are all NP-complete.

The forcing number of a perfect matching $M$ in a graph $G$ is the smallest number of edges inside $M$ that can not be contained in other perfect matchings. The anti-forcing number of $M$ is the smallest number of edges outside $M$ whose removal results in a subgraph with a single perfect matching, that is $M$. Recently, in order to investigate the distributions of forcing numbers and anti-forcing numbers, the forcing polynomial and anti-forcing polynomial were proposed, respectively. In this work, the forcing and anti-forcing polynomials of a polyomino graph are obtained. As consequences, the forcing and anti-forcing spectra of this polyomino graph are determined, and the asymptotic behaviors on the degree of freedom and the sum of all anti-forcing numbers are revealed, respectively.

The balanced hypercube $BH_n$, a variant of the hypercube, was proposed as a desired interconnection network topology. It is known that $BH_n$ is bipartite. Assume that $S=\{s_1,s_2,\cdots,s_{2n-2}\}$ and $T=\{t_1,t_2,\cdots,t_{2n-2}\}$ are any two sets of vertices in different partite sets of $BH_n$ ($n\geq2$). It has been proved that there exists paired 2-disjoint path cover of $BH_n$. In this paper, we prove that there exists unpaired $(2n-2)$-disjoint path cover of $BH_n$ ($n\geq2$) from $S$ to $T$, which improved some known results. The upper bound $2n-2$ of the number of disjoint paths in unpaired $(2n-2)$-disjoint path cover is best possible., Comment: arXiv admin note: text overlap with arXiv:1804.01949

Dong and Wang in [Theor. Comput. Sci. 771 (2019) 93--98] conjectured that the resulting graph of the $n$-dimensional folded hypercube $FQ_n$ by deleting any perfect matching is isomorphic to the hypercube $Q_n$. In this paper, we show that the conjecture holds when $n=2,3$, and it is not true for $n\geq4$.

The restricted hypercube-like graphs, variants of the hypercube, were proposed as desired interconnection networks of parallel systems. The matching preclusion number of a graph is the minimum number of edges whose deletion results in the graph with neither perfect matchings nor almost perfect matchings. The fractional perfect matching preclusion and fractional strong perfect matching preclusion are generalizations of the concept matching preclusion. In this paper, we obtain fractional matching preclusion number and fractional strong matching preclusion numbers of restricted hypercube-like graphs, which extend some known results.

The connectivity of a network directly signifies its reliability and fault-tolerance. Structure and substructure connectivity are two novel generalizations of the connectivity. Let $H$ be a subgraph of a connected graph $G$. The structure connectivity (resp. substructure connectivity) of $G$, denoted by $\kappa(G;H)$ (resp. $\kappa^s(G;H)$), is defined to be the minimum cardinality of a set $F$ of connected subgraphs in $G$, if exists, whose removal disconnects $G$ and each element of $F$ is isomorphic to $H$ (resp. a subgraph of $H$). In this paper, we shall establish both $\kappa(BH_n;H)$ and $\kappa^s(BH_n;H)$ of the balanced hypercube $BH_n$ for $H\in\{K_1,K_{1,1},K_{1,2},K_{1,3},C_4\}$., Comment: arXiv admin note: text overlap with arXiv:1805.08461

Edge-connectivity is a classic measure for reliability of a network in the presence of edge failures. $k$-restricted edge-connectivity is one of the refined indicators for fault tolerance of large networks. Matching preclusion and conditional matching preclusion are two important measures for the robustness of networks in edge fault scenario. In this paper, we show that the DCell network $D_{k,n}$ is super-$\lambda$ for $k\geq2$ and $n\geq2$, super-$\lambda_2$ for $k\geq3$ and $n\geq2$, or $k=2$ and $n=2$, and super-$\lambda_3$ for $k\geq4$ and $n\geq3$. Moreover, as an application of $k$-restricted edge-connectivity, we study the matching preclusion number and conditional matching preclusion number, and characterize the corresponding optimal solutions of $D_{k,n}$. In particular, we have shown that $D_{1,n}$ is isomorphic to the $(n,k)$-star graph $S_{n+1,2}$ for $n\geq2$., Comment: 20 pages, 1 figure

The restricted $h$-connectivity of a graph $G$, denoted by $\kappa^h(G)$, is defined as the minimum cardinality of a set of vertices $F$ in $G$, if exists, whose removal disconnects $G$ and the minimum degree of each component of $G-F$ is at least $h$. In this paper, we study the restricted $h$-connectivity of the balanced hypercube $BH_n$ and determine that $\kappa^1(BH_n)=\kappa^2(BH_n)=4n-4$ for $n\geq2$. We also obtain a sharp upper bound of $\kappa^3(BH_n)$ and $\kappa^4(BH_n)$ of $n$-dimension balanced hypercube for $n\geq3$ ($n\neq4$). In particular, we show that $\kappa^3(BH_3)=\kappa^4(BH_3)=12$.

For a graph $G$ with $n$ vertices, let $\nu(G)$ and $A(G)$ denote the matching number and adjacency matrix of $G$, respectively. The permanental polynomial of $G$ is defined as $\pi(G,x)={\rm per}(Ix-A(G))$. The permanental nullity of $G$, denoted by $\eta_{per}(G)$, is the multiplicity of the zero root of $\pi(G,x)$. In this paper, we use the Gallai-Edmonds structure theorem to derive a concise formula which reveals the relationship between the permanental nullity and the matching number of a graph. Furthermore, we prove a necessary and sufficient condition for a graph $G$ to have $\eta_{per}(G)=0$. As applications, we show that every unicyclic graph $G$ on $n$ vertices satisfies $n-2\nu(G)-1 \le \eta_{per}(G) \le n-2\nu(G)$, that the permanental nullity of the line graph of a graph is either zero or one, and that the permanental nullity of a factor critical graph is always zero.

The matching energy is defined as the sum of the absolute values of the zeros of the matching polynomial of a graph, which is proposed first by Gutman and Wagner [The matching energy of a graph, Discrete Appl. Math. 160 (2012) 2177--2187]. And they gave some properties and asymptotic results of the matching energy. In this paper, we characterize the trees with $n$ vertices whose complements have the maximal, second-maximal and minimal matching energy. Further, we determine the trees with a perfect matching whose complements have the second-maximal matching energy. In particular, show that the trees with edge-independence number number $p$ whose complements have the minimum matching energy for $p=1,2,\ldots, \lfloor\frac{n}{2}\rfloor$., Comment: 14 pages, 7 figures