Some general models of traffic flow in an isolated network

Starting form basic principles, we obtain mathematical models that describe the traffic of material objects in a network represented by a graph. We analyze existence, uniqueness, and positivity of solutions for some implicit models. Also, some linear models and their equilibria are analyzed. Copyright © 2017 John Wiley & Sons, Ltd.     

Classification of Vertex‐Transitive Cubic Partial Cubes

Partial cubes are graphs isometrically embeddable into hypercubes. In this article, it is proved that every cubic, vertex‐transitive partial cube is isomorphic to one of the following graphs: , for , the generalized Petersen graph G (10, 3), the cubic permutahedron, the truncated cuboctahedron, or the truncated icosidodecahedron. This classification is a generalization of results of Bre?ar et  al. (Eur J Combin 25 (2004), 55–64) on cubic mirror graphs; it includes all cubic, distance‐regular partial cubes (P. M. Weichsel, Discrete Math 109 (1992), 297–306), and presents a contribution to the classification of all cubic partial cubes.     

On (4, 2)‐Choosable Graphs

A graph G is called ‐choosable if for any list assignment L that assigns to each vertex v a set of a permissible colors, there is a b‐tuple L‐coloring of G . An (a , 1)‐choosable graph is also called a‐choosable. In the pioneering article on list coloring of graphs by Erd?s et al.  2 , 2‐choosable graphs are characterized. Confirming a special case of a conjecture in  2 , Tuza and Voigt  3 proved that 2‐choosable graphs are ‐choosable for any positive integer m . On the other hand, Voigt 6 proved that if m is an odd integer, then these are the only ‐choosable graphs; however, when m is even, there are ‐choosable graphs that are not 2‐choosable. A graph is called 3‐choosable‐critical if it is not 2‐choosable, but all its proper subgraphs are 2‐choosable. Voigt conjectured that for every positive integer m , all bipartite 3‐choosable‐critical graphs are ‐choosable. In this article, we determine which 3‐choosable‐critical graphs are (4, 2)‐choosable, refuting Voigt's conjecture in the process. Nevertheless, a weaker version of the conjecture is true: we prove that there is an even integer k such that for any positive integer m , every bipartite 3‐choosable‐critical graph is ‐choosable. Moving beyond 3‐choosable‐critical graphs, we present an infinite family of non‐3‐choosable‐critical graphs that have been shown by computer analysis to be (4, 2)‐choosable. This shows that the family of all (4, 2)‐choosable graphs has rich structure.     

A Relaxed Version of the Erdős–Lovász Tihany Conjecture

The Erd?s–Lovász Tihany conjecture asserts that every graph G with ) contains two vertex disjoint subgraphs G ₁ and G ₂ such that and . Under the same assumption on G , we show that there are two vertex disjoint subgraphs G ₁ and G ₂ of G such that (a) and or (b) and . Here, is the chromatic number of is the clique number of G , and col(G ) is the coloring number of G .     

Partial Characterizations of 1‐Perfectly Orientable Graphs

We study the class of 1‐perfectly orientable graphs, that is, graphs having an orientation in which every out‐neighborhood induces a tournament. 1‐perfectly orientable graphs form a common generalization of chordal graphs and circular arc graphs. Even though they can be recognized in polynomial time, little is known about their structure. In this article, we develop several results on 1‐perfectly orientable graphs. In particular, we (i) give a characterization of 1‐perfectly orientable graphs in terms of edge clique covers, (ii) identify several graph transformations preserving the class of 1‐perfectly orientable graphs, (iii) exhibit an infinite family of minimal forbidden induced minors for the class of 1‐perfectly orientable graphs, and (iv) characterize the class of 1‐perfectly orientable graphs within the classes of cographs and of cobipartite graphs. The class of 1‐perfectly orientable cobipartite graphs coincides with the class of cobipartite circular arc graphs.     

Flows and Bisections in Cubic Graphs

A k‐weak bisection of a cubic graph G is a partition of the vertex‐set of G into two parts V₁ and V₂ of equal size, such that each connected component of the subgraph of G induced by () is a tree of at most vertices. This notion can be viewed as a relaxed version of nowhere‐zero flows, as it directly follows from old results of Jaeger that every cubic graph G with a circular nowhere‐zero r‐flow has a ‐weak bisection. In this article, we study problems related to the existence of k‐weak bisections. We believe that every cubic graph that has a perfect matching, other than the Petersen graph, admits a 4‐weak bisection and we present a family of cubic graphs with no perfect matching that do not admit such a bisection. The main result of this article is that every cubic graph admits a 5‐weak bisection. When restricted to bridgeless graphs, that result would be a consequence of the assertion of the 5‐flow Conjecture and as such it can be considered a (very small) step toward proving that assertion. However, the harder part of our proof focuses on graphs that do contain bridges.     

Student-like models for risky asset with dependence

We present a new construction of the Student and Student-like fractal activity time model for risky asset. The construction uses the diffusion processes and their superpositions and allows for specified exact Student or Student-like marginal distributions of the returns and for flexible and tractable dependence structure. The fractal activity time is asymptotically self-similar, which is a desired feature seen in practice.     

Reducing an arbitrary fullerene to the dodecahedron

Viewing fullerenes as plane graphs with facial cycles being pentagonal and hexagonal only, it is shown how to reduce an arbitrary fullerene to the (graph of the) dodecahedron. This can be achieved by a sequence of eight reduction steps, seven of which are local operations and the remaining reduction step acts globally. In any case, the resulting algorithm has polynomial running time.     

A new formula for the decycling number of regular graphs

The decycling number $?\left(G\right)$ of a graph $G$ is the smallest number of vertices which can be removed from $G$ so that the resultant graph contains no cycle. A decycling set containing exactly $?\left(G\right)$ vertices of $G$ is called a $?$-set. For any decycling set $S$ of a $k$-regular graph $G$, we show that $\left|S\right|=\frac{\beta \left(G\right)+m\left(S\right)}{k?1}$, where $\beta \left(G\right)$ is the cycle rank of $G$, $m\left(S\right)=c+\left|E\left(S\right)\right|?1$ is the margin number of $S$, $c$ and $\left|E\left(S\right)\right|$ are, respectively, the number of components of $G?S$ and the number of edges in $G\left[S\right]$. In particular, for any $?$-set $S$ of a 3-regular graph $G$, we prove that $m\left(S\right)=\xi \left(G\right)$, where $\xi \left(G\right)$ is the Betti deficiency of $G$. This implies that the decycling number of a 3-regular graph $G$ is $\frac{\beta \left(G\right)+\xi \left(G\right)}{2}$. Hence $?\left(G\right)=?\frac{\beta \left(G\right)}{2}?$ for a 3-regular upper-embeddable graph $G$, which concludes the results in [Gao et al., 2015, Wei and Li, 2013] and solves two open problems posed by Bau and Beineke (2002). Considering an algorithm by Furst et al., (1988), there exists a polynomial time algorithm to compute $Z\left(G\right)$, the cardinality of a maximum nonseparating independent set in a $3$-regular graph $G$, which solves an open problem raised by Speckenmeyer (1988). As for a 4-regular graph $G$, we show that for any $?$-set $S$ of $G$, there exists a spanning tree $T$ of $G$ such that the elements of $S$ are simply the leaves of $T$ with at most two exceptions providing $?\left(G\right)=?\frac{\beta \left(G\right)}{3}?$. On the other hand, if $G$ is a loopless graph on $n$ vertices with maximum degree at most $4$, then

The above two upper bounds are tight, and this makes an extension of a result due to Punnim (2006).     

Gonality of complete graphs with a small number of omitted edges

Let be the complete metric graph on d vertices. We compute the gonality of graphs obtained from by omitting edges forming a , or general configurations of at most edges. We also investigate if these graphs can be lifted to curves with the same gonality. We lift the former graphs and the ones obtained by removing up to edges not forming a K ₃ using models of plane curves with certain singularities. We also study the gonality when removing edges not forming a K ₃. We use harmonic morphism to lift these graphs to curves with the same gonality because in this case plane singular models can no longer be used due to a result of Coppens and Kato.