A theta graph θ r , p , q is the graph obtained by connecting two distinct vertices with three internally disjoint paths of length r , p , q , where q ≥ p ≥ r ≥ 1 and p ≥ 2 . A graph is θ r , p , q -free if it does not contain θ r , p , q as a subgraph. The maximum spectral radius of θ 1 , p , q -free graphs with given size has been determined for any q ≥ p ≥ 2 . Zhai et al. (2021) characterized the extremal graph with the maximum spectral radius of θ 2 , 2 , 2 -free graphs having m edges. In this paper, we determine the maximum spectral radius of θ 2 , 2 , 3 -free graphs with size m and characterize the extremal graph.

For integers $k$ and $d$ with $k\ge 2d>0$, a circular ${k}/{d}$-flow of a graph $G$ is an orientation together with a mapping from $E(G)$ to $\{\pm d, \pm (d+1),\ldots,\pm (k-d)\}$ such that, for each vertex of $G$, the sum of images on outgoing edges is equal to the sum of images on incoming edges. Related to the four color problem, a classical result of Tutte shows that a cubic graph admits a circular $4/1$-flow if and only if it is Class I (i.e., $3$-edge-colorable). Tutte's $3$-flow conjecture implies that every $5$-regular Class I graph admits a nowhere-zero $3$-flow (equivalently, a circular $6/2$-flow) as a special case. Steffen in 2015 conjectured that every $(2t+1)$-regular Class I graph admits a circular $(2t+2)/t$-flow. He also proposed a more general conjecture that every $(2t+1)$-odd-edge-connected $(2t+1)$-regular graph admits a circular $(2t+2)/t$-flow for any integer $t\ge 2$, which includes the circular flow conjecture of Jaeger (1981) stating that every $2t$-edge-connected graph admits a circular $(2t+2)/t$-flow for any even $t\ge 2$. Jaeger's conjecture was disproved in 2018 for all even $t\ge 6$, and based on these results, Mattiolo and Steffen recently constructed counterexamples to Steffen's conjecture for Class I graphs when $t=4k+2$ for any integer $k\ge 1$. In this paper, we extend the above results and construct infinitely many $2t$-edge-connected $(2t+1)$-regular Class I graphs without circular $(2t+2)/t$-flows for any integer $t\in \{6,8,10\}$ or $t\geq 12$. Our result provides more general counterexamples to Steffen's two conjectures for both even and odd $t$ and simultaneously generalizes the counterexamples of Jaeger's circular flow conjecture to regular Class I graphs.

The ‐rainbow index of a graph G was introduced by Chartrand et al. (Network 54(2) (2009), 75–81; 55 (2010), 360–367). For the complete graph Kn of order , they showed that for . Furthermore, they conjectured that for every positive integer , there exists a positive integer N such that for every integer . More generally, they conjectured that for every pair of positive integers k and with , there exists a positive integer N such that for every integer . This article provides solutions to these conjectures. © 2013 Wiley Periodicals, Inc. NETWORKS, Vol. 62(3), 220–224 2013

In this correspondence, we use a symplectic geometry over the binary field to discuss the equivalence of additive codes over the quaternary field and the equivalence of additive quantum codes. We establish the existence of a standard form of the stabilizer and the normalizer matrices for additive quantum codes. Thus, we present the quantum analogue of standard forms of generator and parity check matrices for systematic linear codes in classical coding theory for additive quantum codes.

The minimum all-ones problem was shown to be NP-complete for general graphs. Therefore, it becomes an interesting problem to identify special classes of graphs for which one can find polynomial time algorithms. In this paper we consider this problem for trees. First, for any solution to the all-ones problem for a tree, we give a characterization of the elements in the solution by introducing the concept of the quasi all-ones problem. Then we give the enumeration for the number of solutions in a tree. By using the minimum odd (even) sum problem as subprocess, we obtain a linear time algorithm for the minimum all-ones problem for trees. We also get a linear time algorithm for finding solutions to the all-ones problem in a unicyclic graph.

We give elementary recursive constructions of binary self-orthogonal codes with dual distance four for all even lengths n/spl ges/12 and n=8. Consequently, good quantum codes of minimum distance three and four for such length n are obtained via Steane's construction and the CSS construction. Previously, such quantum codes were explicitly constructed only for a sparse set of lengths. Almost all of our quantum codes of minimum distance three are optimal or near optimal, and some of our minimum-distance four quantum codes are better than or comparable with those known before.

In this paper, we give solutions for the two conjectures on the inverse problem of the Wiener index of peptoids proposed by Goldman et al. We give the first conjecture a positive proof and the second conjecture a negative answer.

Let D be a digraph with minimum indegree at least one. The following results are proved: a digraph D has a semikernel if and only if its line digraph $L(D)$ does; the number of (k,1)-kernels in L(D) is less than or equal to that in D; if the number of (k,l)-kernels in D is less than or equal to the number of (2,l)-kernels in L(D), and if L(D) has a (k,l)-kernel, then D has a (k',l')-kernel for $k'+l\leq k$, $l\leq l'$. As a consequence, it obtains previous results about kernels and quasikernels in the line digraph. It is also proved that any digraph has a (k,l)-kernel with $l\geq 2k-2$, $k\geq 1$, generalizing a previous result on the existence of quasikernels in digraphs.