Search

The irregularity strength of a graph $G$, $s(G)$, is the least $k$ admitting a $\{1,2,\ldots,k\}$-weighting of the edges of $G$ assuring distinct weighted degrees of all vertices, or equivalently the least possible maximal edge multiplicity in an irregular multigraph obtained of $G$ via multiplying some of its edges. The most well-known open problem concerning this graph invariant is the conjecture posed in 1987 by Faudree and Lehel that there exists a constant $C$ such that $s(G)\leq \frac{n}{d}+C$ for each $d$-regular graph $G$ with $n$ vertices and $d\geq 2$ (while a straightforward counting argument yields $s(G)\geq \frac{n+d-1}{d}$). The best known results towards this imply that $s(G)\leq 6\lceil\frac{n}{d}\rceil$ for every $d$-regular graph $G$ with $n$ vertices and $d\geq 2$, while $s(G)\leq (4+o(1))\frac{n}{d}+4$ if $d\geq n^{0.5}\ln n$. We show that the conjecture of Faudree and Lehel holds asymptotically in the cases when $d$ is neither very small nor very close to $n$. We in particular prove that for large enough $n$ and $d\in [\ln^8n,\frac{n}{\ln^3 n}]$, $s(G)\leq \frac{n}{d}(1+\frac{8}{\ln n})$, and thereby we show that $s(G) = \frac{n}{d}(1+o(1))$ then. We moreover prove the latter to hold already when $d\in [\ln^{1+\varepsilon}n,\frac{n}{\ln^\varepsilon n}]$ where $\varepsilon$ is an arbitrary positive constant., 14 pages

Recently, Kawarabayashi and Thorup presented the first deterministic edge-connectivity recognition algorithm in near-linear time. A crucial step in their algorithm uses the existence of vertex subsets of a simple graph $G$ on $n$ vertices whose contractions leave a multigraph with $\tilde{O}(n/\delta)$ vertices and $\tilde{O}(n)$ edges that preserves all non-trivial min-cuts of $G$, where $\delta$ is the minimum degree of $G$ and $\tilde{O}$ hides logarithmic factors. We present a simple argument that improves this contraction-based sparsifier by eliminating the poly-logarithmic factors, that is, we show a contraction-based sparsification that leaves $O(n/\delta)$ vertices and $O(n)$ edges, preserves all non-trivial min-cuts and can be computed in near-linear time $\tilde{O}(m)$, where $m$ is the number of edges of $G$. We also obtain that every simple graph has $O((n/\delta)^2)$ non-trivial min-cuts. Our approach allows to represent all non-trivial min-cuts of a graph by a cactus representation, whose cactus graph has $O(n/\delta)$ vertices. Moreover, this cactus representation can be derived directly from the standard cactus representation of all min-cuts in linear time. We apply this compact structure to show that all min-cuts can be explicitly listed in $\tilde{O}(m) + O(n^2 / \delta)$ time for every simple graph, which improves the previous best time bound $O(nm)$ given by Gusfield and Naor., Comment: 12 pages, 3 figures

A propositional logic sentence in conjunctive normal form that has clauses of length two (a 2-CNF) can be associated with a multigraph in which the vertices correspond to the variables and edges to clauses. We first show that every such sentence that has been reduced, that is, which is unchanged under application of certain tautologies, is equisatisfiable to a 2-CNF whose associated multigraph is, in fact, a simple graph. Our main result is a complete characterization of graphs that can support unsatisfiable 2-CNF sentences. We show that a simple graph can support an unsatisfiable reduced 2-CNF sentence if and only if it contains any one of four specific small graphs as a topological minor. Equivalently, all reduced 2-CNF sentences supported on a given simple graph are satisfiable if and only if all subdivisions of those four graphs are forbidden as subgraphs of of the original graph. We conclude with a discussion of why the Robertson-Seymour graph minor theorem does not apply in our approach., Corrected error in Theorem 5 of previous version (Theorem 7 in this version). One direction of the result was incorrect. As a result, one more graph was included in the main result, Theorem 18 of previous version (Theorem 20 in this version)

It is well known that if $$G = (V, E)$$ G = ( V , E ) is a connected multigraph and $$X\subset V$$ X ⊂ V is a subset of even order, then G contains a spanning forest H such that each vertex from X has an odd degree in H and all the other vertices have an even degree in H. This spanning forest may have isolated vertices. If this is not allowed in H, then the situation is much more complicated. In this paper, we study this problem and generalize the concepts of even-factors and odd-factors in a unified form.

For a fixed positive integer p , a coloring of the edges of a multigraph G is called p -acyclic coloring if every cycle C in G contains at least min { | C | , p + 1 } colors. The least number of colors needed for a p -acyclic coloring of G is the p -arboricity of G . From a result of Bartnicki et al. (2019) it follows that there are planar graphs with unbounded p -arboricity. In this note we relax the definition of p -arboricity for plane multigraphs in sense that the requirement is not for all cycles but only for facial cycles and show that the smallest number of colors needed for such a coloring is a constant (depending on p only).

Let G be a tripartite graph with tripartition $$(V_{1},V_{2},V_{3})$$ , where $$\mid V_{1}\mid =\mid V_{2}\mid =\mid V_{3}\mid =k>0$$ . It is proved that if $$d(x)+d(y)\ge 3k$$ for every pair of nonadjacent vertices $$x\in V_{i}, y\in V_{j}$$ with $$i\ne j(i,j\in \{1,2,3\})$$ , then G contains k vertex-disjoint triangles. As a corollary, if $$d(x)\ge \frac{3}{2}k$$ for each vertex $$x\in V(G)$$ , then G contains k vertex-disjoint triangles. Based on the above results, vertex-disjoint triangles in multigraphs are studied. Let M be a standard tripartite multigraph with tripartition $$(V_{1},V_{2},V_{3})$$ , where $$\mid V_{1} \mid =\mid V_{2}\mid =\mid V_{3} \mid =k>0$$ . If $$\delta (M)\ge 3k-1$$ for even k and $$\delta (M)\ge 3k$$ for odd k, then M contains k vertex-disjoint 4-triangles $$\varDelta _{4}$$ (a triangle with at least four edges). Furthermore, examples are given showing that the degree conditions of all our three results are best possible.

We prove that if a directed multigraph $D$ has at most $t$ pairwise arc-disjoint directed triangles, then there exists a set of less than $2t$ arcs in $D$ which meets all directed triangles in $D$, except in the trivial case $t=0$. This answers affirmatively a question of Tuza from 1990., 4 pages, 1 figure. The previous version had an error in the argument for the strict inequality in the case where digons are permitted; this version fixes the error

Given a multigraph $$G=(V,E)$$, the edge cover packing problem (ECPP) on G is to find a coloring of edges of G using the maximum number of colors such that at each vertex all colors occur. ECPP can be formulated as an integer program and is NP-hard in general. In this paper, we consider the fractional edge cover packing problem, the LP relaxation of ECPP. We focus on the more general weighted setting, the weighted fractional edge cover packing problem (WFECPP), which can be formulated as the following linear program $$\begin{aligned} \begin{array}{ll} \hbox {Maximize} \ \ \ &{} {{\varvec{1}}}^T {{\varvec{x}}} \\ \hbox {subject to} &{} A{{\varvec{x}}} \le {{\varvec{w}}} \\ &{} \quad {{\varvec{x}}} \ge {{\varvec{0}}}, \end{array} \end{aligned}$$where A is the edge–edge cover incidence matrix of G, $${\varvec{w}}=(w(e): e\in E)$$, and w(e) is a positive rational weight on each edge e of G. The weighted co-density problem, closely related to WFECPP, is to find a subset $$S\subseteq V$$ with $$|S|\ge 3$$ and odd, such that $$\frac{2w(E^{+}(S))}{|S|+1}$$ is minimized, where $$E^{+}(S)$$ is the set of all edges of G with at least one end in S and $$w(E^{+}(S))$$ is the total weight of all edges in $$E^{+}(S)$$. We present polynomial combinatorial algorithms for solving these two problems exactly.

In view of the interesting applications of alternating Euler trails, it is natural to ask about the existence of Euler trails fulfilling some restriction other than alternating. Let H be a graph possibly with loops and G a multigraph without loops. G is said to be H-colored if there exists a function $$c:E(G) \rightarrow V(H)$$ . A trail $$W = (v_0, e_0, v_1, e_1, \ldots , e_{k-1}, v_k)$$ in G is an H-trail if and only if $$(c(e_0), a_0, c(e_1), \ldots , c(e_{k-2}), a_{k-2}, c(e_{k-1}))$$ is a walk in H with $$a_i=c(e_{i})c(e_{i+1})$$ for every i in $$\{0, \ldots , k-2\}$$ . In particular an H-trail is a properly colored trail when H is a complete graph without loops. An H-trail $$T = (v_0, e_0, v_1, e_1, \ldots , e_{k-1}, v_k)$$ is a closedH-trail if $$v_0=v_k$$ , and $$c(e_{k-1}$$ ) and $$c(e_0)$$ are adjacent in H. A closed H-trail, T, is a closed EulerH-trail if $$E(T)=E(G)$$ . In order to see that H-coloring theory is related to the automata theory, let each vertex represents a state and each edge of H represents an allowed transition. This implies that an H-walk in a multigraph G is a predetermined sequence of allowed operations. Another interesting application goes as follows: a safe route conducted by a health inspector in a hospital (a route where the inspector does not carry bacteria from one area to another, in which can be deadly the spread such a bacteria) is given whenever the multigraph associated with the map of the hospital be an eulerian graph and it has a closed Euler H-trail for some well chosen H. Because of applications of Euler H-trails, it is natural to ask the following: (i) What structural properties of H imply the existence of Euler H-trails? (ii) What structural properties of G, with respect to the H-coloring, imply the existence of Euler H-trails? In this paper, we study Euler H-trails and we will show a characterization of the graphs containing an Euler H-trail. As a consequence of the main result we obtain a classical result proved by Kotzig (Matematicki casopis 18(1):76–80, 1968).

A graph is called P t -free if it does not contain the path on t vertices as an induced subgraph. Let H be a multigraph with the property that any two distinct vertices share at most one common neighbour. We show that the generating function for (list) graph homomorphisms from G to H can be calculated in subexponential time 2 O t n log ( n ) for n = | V ( G ) | in the class of P t -free graphs G . As a corollary, we show that the number of 3-colourings of a P t -free graph G can be found in subexponential time. On the other hand, no subexponential time algorithm exists for 4-colourability of P t -free graphs assuming the Exponential Time Hypothesis. Along the way, we prove that P t -free graphs have pathwidth that is linear in their maximum degree.

In connection to the 5-flow conjecture, a modulo 5-orientation of a graph G is an orientation of G such that the indegree is congruent to outdegree modulo 5 at each vertex. Jaeger conjectured that every 9-edge-connected multigraph admits a modulo 5-orientation, whose truth would imply Tutte’s 5-flow conjecture. In this paper, we study the problem of modulo 5-orientation for given multigraphic degree sequences. We prove that a multigraphic degree sequence d = ( d 1 , … , d n ) has a realization G with a modulo 5-orientation if and only if d i ≠ 1 , 3 for each i . In addition, we show that every multigraphic sequence d = ( d 1 , … , d n ) with min 1 ≤ i ≤ n d i ≥ 9 has a 9-edge-connected realization which admits a modulo 5-orientation for every possible boundary function. This supports the above mentioned conjecture of Jaeger.

For a graph G, let $$f_2(G)$$ denote the largest number of vertices in a 2-regular subgraph of G. We determine the minimum of $$f_2(G)$$ over 3-regular n-vertex simple graphs G. To do this, we prove that every 3-regular multigraph with exactly c cut-edges has a 2-regular subgraph that omits at most $$\max \{0,\lfloor (c-1)/2\rfloor \}$$ vertices. More generally, every n-vertex multigraph with maximum degree 3 and m edges has a 2-regular subgraph that omits at most $$\max \{0,\lfloor (3n-2m+c-1)/2\rfloor \}$$ vertices. These bounds are sharp; we describe the extremal multigraphs.

Let $G=(V(G), E(G))$ be a multigraph with maximum degree $\Delta(G)$, chromatic index $\chi'(G)$ and total chromatic number $\chi''(G)$. The Total Coloring conjecture proposed by Behzad and Vizing, independently, states that $\chi''(G)\leq \Delta(G)+\mu(G) +1$ for a multigraph $G$, where $\mu(G)$ is the multiplicity of $G$. Moreover, Goldberg conjectured that $\chi''(G)=\chi'(G)$ if $\chi'(G)\geq \Delta(G)+3$ and noticed the conjecture holds when $G$ is an edge-chromatic critical graph. By assuming the Goldberg-Seymour conjecture, we show that $\chi''(G)=\chi'(G)$ if $\chi'(G)\geq \max\{ \Delta(G)+2, |V(G)|+1\}$ in this note. Consequently, $\chi''(G) = \chi'(G)$ if $\chi'(G) \ge \Delta(G) +2$ and $G$ has a spanning edge-chromatic critical subgraph.

Let $G$ be an (oriented) graph on the vertex set $V = \{ 0, 1,\ldots,n\}$ with root $0$. Postnikov and Shapiro associated a monomial ideal $\mathcal{M}_G$ in the polynomial ring $ R = {\mathbb{K}}[x_1,\ldots,x_n]$ over a field $\mathbb{K}$. A subideal $\mathcal{M}_G^{(k)}$ of $\mathcal{M}_G$ generated by subsets of $\widetilde{V}=V\setminus \{0\}$ of size at most $k+1$ is called a $k$-skeleton ideal of the graph $G$. Many interesting homological and combinatorial properties of $1$-skeleton ideal $\mathcal{M}_G^{(1)}$ are obtained by Dochtermann for certain classes of simple graph $G$. A finite sequence $\mathcal{P}=(p_1,\ldots,p_n) \in \mathbb{N}^n$ is called a spherical $G$-parking function if the monomial $\mathbf{x}^{\mathcal{P}} = \prod_{i=1}^{n} x_i^{p_i} \in \mathcal{M}_G \setminus \mathcal{M}_G^{(n-2)}$. Let ${\rm sPF}(G)$ be the set of all spherical $G$-parking functions. In this paper, a combinatorial description for all multigraded Betti numbers of the $k$-skeleton ideal $\mathcal{M}_{K_{n+1}}^{(k)}$ of the complete graph $K_{n+1}$ on $V$ are given. Also, using DFS burning algorithms of Perkinson-Yang-Yu (for simple graph) and Gaydarov-Hopkins (for multigraph), we give a combinatorial interpretation of spherical $G$-parking functions for the graph $G = K_{n+1}- \{e\}$ obtained from the complete graph $K_{n+1}$ on deleting an edge $e$. In particular, we showed that $|{\rm sPF}(K_{n+1}- \{e_0\} )|= (n-1)^{n-1}$ for an edge $e_0$ through the root $0$, but $|{\rm sPF}(K_{n+1} - \{e_1\})| = (n-1)^{n-3}(n-2)^2$ for an edge $e_1$ not through the root., 20 pages

The study of a variation of the marking game, in which the first player marks vertices and the second player marks edges of an undirected graph was proposed by Bartnicki et al. (Electron J Combin 15:R72, 2008). In this game, the goal of the second player is to mark as many edges around an unmarked vertex as possible, while the first player wants just the opposite. In this paper, we prove various bounds for the corresponding graph invariant, the vertex-edge coloring number $${\text {col}}_\mathrm{ve}(G)$$ of a graph G. In particular, every (finite or infinite) graph G whose edges can be oriented in such a way that the maximum out-degree is bounded by an integer d has $${\text {col}}_\mathrm{ve}(G)\le d+2$$ . We investigate this invariant in (classes of) planar graphs, including some infinite lattices. We present a close connection between the vertex-edge coloring number of a graph G and the game coloring number of the subdivision graph S(G). In our main result, we bound the vertex-edge coloring number in complete graphs from below and from above, and while $${\text {col}}_\mathrm{ve}(K_n)\le \lceil \log _2{n}\rceil +2$$ , the difference between the upper and the lower bound is roughly $$\log _2(\log _2 n)$$ . The latter results are, in fact, true for any multigraph whose underlying graph is $$K_n$$ .

A k -bisection of a graph G is a partition of its vertex set into two parts V 1 and V 2 of the same cardinality such that every connected component of the subgraph of G induced by V i ( i = 1 , 2 ) has at most k vertices. Ban and Linial conjectured that every bridgeless cubic simple graph admits a 2-bisection except for the Petersen graph. Recently, Abreu et al. showed that Ban–Linial’s conjecture is true for bridgeless claw-free cubic simple graphs. In this short note, we prove a stronger result. We show that for any (not necessarily bridgeless) claw-free cubic multigraph G and for any edge e ∈ E ( G ) , there exists a 2-bisection of G such that the two endvertices of e belong to different parts.

Let G be a directed graph with an integral cost on each edge. For a given positive integer k, the k-length negative cost cycle (kLNCC) problem is to determine whether G contains a negative cost cycle with at least k edges. Because of its applications in deadlock avoidance in synchronized streaming computing network, kLNCC was first studied in paper (Li et al. in Proceedings of the 22nd ACM symposium on parallelism in algorithms and architectures, pp 243–252, 2010), but remains open whether the problem is $${\mathcal{NP}}$$ -hard. In this paper, we first show that an even harder problem, the fixed-point k-length negative cost cycle trail (FPkLNCCT) problem that is to determine whether G contains a negative closed trail enrouting a given vertex (as the fixed point) and containing only cycles with at least k edges, is $${\mathcal{NP}}$$ -complete in a multigraph even when $$k=3$$ by reducing from the 3SAT problem. Then, we prove the $${\mathcal{NP}}$$ -completeness of kLNCC by giving a more sophisticated reduction from the 3 occurrence 3-satisfiability (3O3SAT) problem which is known $${\mathcal{NP}}$$ -complete. The complexity result for kLNCC is interesting since polynomial-time algorithms are known for both 2LNCC, which is actually equivalent to negative cycle detection, and the k-cycle problem, which is to determine whether G contains a cycle with of length at least k. Thus, this paper closes the open problem proposed by Li et al. (2010) whether kLNCC admits polynomial-time algorithms. Last but not the least, we present for 3LNCC a randomized algorithm that, if G contains a negative cycle of length at most L, can find a solution with a probability $$1-\epsilon $$ for any $$\epsilon \in (0,\,1]$$ within runtime $$O(2^{\min \{L,\,h\}}mn\left\lceil \ln \frac{1}{\epsilon }\right\rceil )$$ , where m, n and h are respectively the numbers of edges, vertices and length 2 negative cost cycles in G.

Dvo\v{r}\'{a}k and Postle \cite{DP} introduced a \textit{DP-coloring} of a simple graph as a generalization of a list-coloring. They proved a Brooks' type theorem for a DP-coloring, and Bernshteyn, Kostochka and Pron \cite{BKP} extended it to a DP-coloring of multigraphs. However, detailed structure when a multigraph does not admit a DP-coloring was not specified in \cite{BKP}. In this note, we make this point clear and give the complete structure. This is also motivated by the relation to signed coloring of signed graphs.

A matching $M$ in a multigraph $G=(V,E)$ is said to be uniquely restricted if $M$ is the only perfect matching in the subgraph of $G$ induced by $V(M)$ (i.e., the set of vertices saturated by $M$). For any fixed vertex $x_0$ in $G$, there is a bijection from the set of spanning trees of $G$ to the set of uniquely restricted matchings of size $|V|-1$ in $S(G)-x_0$, where $S(G)$ is the bipartite graph obtained from $G$ by subdividing each edge in $G$. Thus the notion "uniquely restricted matchings of a bipartite graph $H$ saturating all vertices in a partite set $X$" can be viewed as an extension of "spanning trees in a connected graph". Motivated by this observation, we extend the notion "G-parking functions" of a connected multigraph to "B-parking functions" $f:X\rightarrow \{-1,0,1,2,\cdots \}$ of a bipartite graph $H$ with a bipartition $(X,Y)$ and find a bijection $\psi$ from the set of uniquely restricted matchings of $H$ to the set of B-parking functions of $H$. We also show that for any uniquely restricted matching $M$ in $H$ with $|M|=|X|$, if $f=\psi(M)$, then $\sum_{x\in X}f(x)$ is exactly the number of elements $y\in Y-V(M)$ which are not externally B-active with respect to $M$ in $H$, where the new notion "externally B-active members with respect to $M$ in $H$" is an extension of "externally active edges with respect to a spanning tree in a connected multigraph"., Comment: 31 pages, 10 figures, 2 tables and 30 references. https://www.sciencedirect.com/science/article/pii/S0097316518300815

Let G be a multigraph with loops, and let e be an edge in G. Let H be the multigraph obtained by contracting along the edge e. Let λ G and λ H be the largest eigenvalues of G and H respectively. A characterisation theorem is given of precisely when λ H λ G , λ H = λ G , or λ H > λ G . In the case where H happens to be a simple graph, then so is G, and the theorem subsumes those of Hoffman–Smith and Gumbrell for subdivision of edges or splitting of vertices of a graph.

We study an edge coloring problem in multigraphs, in which each node incurs a cost equal to the number of appearances of the most frequent color among those received by its incident edges. We seek an edge coloring with a given number w of colors, that minimizes the total cost incurred by the nodes of the multigraph. We consider a class of approximation algorithms for this problem, which are based on orienting the edges of the multigraph, then grouping appropriately the incoming and outgoing edges at each node so as to construct a bipartite multigraph of maximum degree w , and finally obtaining a proper edge coloring of this bipartite multigraph. As shown by Nomikos et al. (2001), simply choosing an arbitrary edge orientation in the first step yields a 2-approximation algorithm. We investigate whether this approximation ratio can be improved by a more careful choice of the edge orientation in the first step. We prove that, assuming a worst-case bipartite edge coloring, this is not possible in the asymptotic sense, as there exists a family of instances in which any orientation gives a solution with cost at least 2 − Θ ( 1 w ) times the optimal. On the positive side, we show how to produce an orientation which results in a solution with cost within a factor of 2 − 1 2 w of the optimal, thus yielding an approximation ratio strictly better than 2. This improvement is important in view of the fact that this graph-theoretic problem models, among others, wavelength assignment to communication requests in multifiber optical star networks. In this context, the parameter w corresponds to the number of available wavelengths per fiber, which is limited in practice due to technological constraints.

The star chromatic index of a multigraph $G$, denoted $\chi'_{s}(G)$, is the minimum number of colors needed to properly color the edges of $G$ such that no path or cycle of length four is bi-colored. A multigraph $G$ is star $k$-edge-colorable if $\chi'_{s}(G)\le k$. Dvo\v{r}\'ak, Mohar and \v{S}\'amal [Star chromatic index, J Graph Theory 72 (2013), 313--326] proved that every subcubic multigraph is star $7$-edge-colorable, and conjectured that every subcubic multigraph should be star $6$-edge-colorable. Kerdjoudj, Kostochka and Raspaud considered the list version of this problem for simple graphs and proved that every subcubic graph with maximum average degree less than $7/3$ is star list-$5$-edge-colorable. It is known that a graph with maximum average degree $14/5$ is not necessarily star $5$-edge-colorable. In this paper, we prove that every subcubic multigraph with maximum average degree less than $12/5$ is star $5$-edge-colorable., Comment: to appear in Discrete Mathematics. arXiv admin note: text overlap with arXiv:1701.04105

A k-partite r-digraph(multipartite multidigraph) (or briefly MMD)(k ≥ 3, r ≥ 1) is the result of assigning a direction to each edge of a k-partite multigraph that is without loops and contains at most r edges between any pair of vertices from distinct parts. Let D(X1, X2, ⋯, Xk) be a k-partite r-digraph with parts Xi = {xi1, xi2, ⋯, xini}, 1 ≤ i ≤ k. Let dxij + and dxij − be respectively the outdegree and indegree of a vertex xij in Xi. Define axij (or simply aij) as aij = dxij + − dxij − as the imbalance of the vertex xij, 1 ≤ j ≤ ni. In this paper, we characterize the imbalances of k-partite r-digraphs and give a constructive and existence criteria for sequences of integers to be the imbalances of some k-partite r-digraph. Also, we show the existence of a k-partite r-digraph with the given imbalance set.

We establish necessary and sufficient conditions for the existence of a decomposition of a complete multigraph into edge-disjoint cycles of specified lengths, or into edge-disjoint cycles of specified lengths and a perfect matching.

Structurally stable (rough) flows on surfaces have only finitely many singularities and finitely many closed orbits, all of which are hyperbolic, and they have no trajectories joining saddle points. The violation of the last property leads to \begin{document}$Ω$\end{document} -stable flows on surfaces, which are not structurally stable. However, in the present paper we prove that a topological classification of such flows is also reduced to a combinatorial problem. Our complete topological invariant is a multigraph, and we present a polynomial-time algorithm for the distinction of such graphs up to an isomorphism. We also present a graph criterion for orientability of the ambient manifold and a graph-associated formula for its Euler characteristic. Additionally, we give polynomial-time algorithms for checking the orientability and calculating the characteristic.

The star chromatic index of a multigraph $G$, denoted $\chi'_{s}(G)$, is the minimum number of colors needed to properly color the edges of $G$ such that no path or cycle of length four is bi-colored. A multigraph $G$ is star $k$-edge-colorable if $\chi'_{s}(G)\le k$. Dvo\v{r}\'ak, Mohar and \v{S}\'amal [Star chromatic index, J. Graph Theory 72 (2013), 313--326] proved that every subcubic multigraph is star $7$-edge-colorable. They conjectured in the same paper that every subcubic multigraph should be star $6$-edge-colorable. In this paper, we first prove that it is NP-complete to determine whether $\chi'_s(G)\le3$ for an arbitrary graph $G$. This answers a question of Mohar. We then establish some structure results on subcubic multigraphs $G$ with $\delta(G)\le2$ such that $\chi'_s(G)>k$ but $\chi'_s(G-v)\le k$ for any $v\in V(G)$, where $k\in\{5,6\}$. We finally apply the structure results, along with a simple discharging method, to prove that every subcubic multigraph $G$ is star $6$-edge-colorable if $mad(G), Comment: to appear in J. Graph Theory

A 1-factorization of the complete multigraph λK2n is said to be indecomposable if it cannot be represented as the union of 1-factorizations of λ0K2n and (λ−λ0)K2n, where λ0

For a graph G and a family of graphs F , the general Kneser graph KG ( G , F ) is a graph with the vertex set consisting of all subgraphs of G isomorphic to some member of F and two vertices are adjacent if their corresponding subgraphs are edge disjoint. In this paper, we introduce some generalizations of Turan number of graphs. In view of these generalizations, we give some lower and upper bounds for the chromatic number of general Kneser graphs KG ( G , F ) . Using these bounds, we determine the chromatic number of some family of general Kneser graphs KG ( G , F ) in terms of generalized Turan number of graphs. In particular, we determine the chromatic number of every Kneser multigraph KG ( G , F ) where G is a multigraph each of whose edges has the multiplicity at least 2 and F is an arbitrary family of simple graphs. Moreover, the chromatic number of general Kneser graph KG ( G , F ) is exactly determined where G is a dense graph and F = { K 1 , 2 } .

A $c$-edge-colored multigraph has each edge colored with one of the $c$ available colors and no two parallel edges have the same color. A proper Hamiltonian cycle is a cycle containing all the vertices of the multigraph such that no two adjacent edges have the same color. In this work we establish sufficient conditions for a multigraph to have a proper Hamiltonian cycle, depending on several parameters such as the number of edges and the rainbow degree., Comment: 13 pages

We prove that if $M$ is a maximal $k$-edge-colorable subgraph of a multigraph $G$ and if $F = \{v \in V(G) : d_M(v) \leq k-\mu(v)\}$, then $d_F(v) \leq d_M(v)$ for all $v \in F$. (When $G$ is a simple graph, the set $F$ is just the set of vertices having degree less than $k$ in $M$.) This implies Vizing's Theorem as well as a special case of Tuza's Conjecture on packing and covering of triangles. A more detailed version of our result also implies Vizing's Adjacency Lemma for simple graphs., Comment: 11 pages, 1 figure. Fixed some inaccurate references to "Vizing's Theorem" (the stronger version cited here is in fact due to Ore), cleared up some muddled results in the section about forests, simplified some notation, and made other various readability improvements

A cycle of length four is called a quadrilateral and a multigraph is called standard if every edge in it has multiplicity at most two. We prove that if M is a standard multigraph of order 4k, where k is a positive integer and the minimum degree of M is at least $$6k-2$$ , then M contains k vertex-disjoint quadrilaterals, such that each quadrilateral contains at least three multiedges, with only two exceptions. This implies the main result obtained by Zhang and Wang [J Graph Theory 50:91–104, 2005]: Let D be a directed graph of order 4k, where k is a positive integer. Suppose that the minimum degree of D is at least $$6k-2$$ , then D contains k vertex-disjoint directed quadrilaterals with only one exception.

Given a $c$-edge-coloured multigraph, a proper Hamiltonian path is a path that contains all the vertices of the multigraph such that no two adjacent edges have the same colour. In this work we establish sufficient conditions for an edge-coloured multigraph to guarantee the existence of a proper Hamiltonian path, involving various parameters as the number of edges, the number of colours, the rainbow degree and the connectivity., 21 pages

We consider a Hamiltonian decomposition problem of partitioning a regular graph into edge-disjoint Hamiltonian cycles. A sufficient condition for vertex adjacency in the 1-skeleton of the traveling salesperson polytope can be formulated as the Hamiltonian decomposition problem in a 4-regular multigraph. We introduce a heuristic general variable neighborhood search algorithm for this problem based on finding a vertex-disjoint cycle cover of the multigraph through reduction to perfect matching and several cycle merging operations. The algorithm has a one-sided error: the answer “not adjacent” is always correct, and was tested on random directed and undirected Hamiltonian cycles and on pyramidal tours.

Let $D(n,r)$ be a random $r$-out regular directed multigraph on the set of vertices $\{1,\ldots,n\}$. In this work, we establish that for every $r \ge 2$, there exists $\eta_r>0$ such that $\text{diam}(D(n,r))=(1+\eta_r+o(1))\log_r{n}$. Our techniques also allow us to bound some extremal quantities related to the stationary distribution of a simple random walk on $D(n,r)$. In particular, we determine the asymptotic behaviour of $\pi_{\max}$ and $\pi_{\min}$, the maximum and the minimum values of the stationary distribution. We show that with high probability $\pi_{\max} = n^{-1+o(1)}$ and $\pi_{\min}=n^{-(1+\eta_r)+o(1)}$. Our proof shows that the vertices with $\pi(v)$ near to $\pi_{\min}$ lie at the top of "narrow, slippery towers", such vertices are also responsible for increasing the diameter from $(1+o(1))\log_r n$ to $(1+\eta_r+o(1))\log_r{n}$., Comment: 31 pages

In this paper, we consider the decomposition of multigraphs under minimum degree constraints and give a unified generalization of several results by various researchers. Let $G$ be a multigraph in which no quadrilaterals share edges with triangles and other quadrilaterals and let $\mu_G(v)=\max\{\mu_G(u,v):u\in V(G)\setminus\{v\}\}$, where $\mu_G(u,v)$ is the number of edges joining $u$ and $v$ in $G$. We show that for any two functions $a,b:V(G)\rightarrow\mathbb{N}\setminus\{0,1\}$, if $d_G(v)\ge a(v)+b(v)+2\mu_G(v)-3$ for each $v\in V(G)$, then there is a partition $(X,Y)$ of $V(G)$ such that $d_X(x)\geq a(x)$ for each $x\in X$ and $d_Y(y)\geq b(y)$ for each $y\in Y$. This extends the related results due to Diwan [3], Liu and Xu [7] and Ma and Yang [10] on simple graphs to the multigraph setting.

A decomposition of a multigraph $G$ is a partition of its edges into subgraphs $G(1), \ldots , G(k)$. It is called an $r$-factorization if every $G(i)$ is $r$-regular and spanning. If $G$ is a subgraph of $H$, a decomposition of $G$ is said to be enclosed in a decomposition of $H$ if, for every $1 \leq i \leq k$, $G(i)$ is a subgraph of $H(i)$. Feghali and Johnson gave necessary and sufficient conditions for a given decomposition of $\lambda K_n$ to be enclosed in some $2$-edge-connected $r$-factorization of $\mu K_{m}$ for some range of values for the parameters $n$, $m$, $\lambda$, $\mu$, $r$: $r=2$, $\mu>\lambda$ and either $m \geq 2n-1$, or $m=2n-2$ and $\mu = 2$ and $\lambda=1$, or $n=3$ and $m=4$. We generalize their result to every $r \geq 2$ and $m \geq 2n - 2$. We also give some sufficient conditions for enclosing a given decomposition of $\lambda K_n$ in some $2$-edge-connected $r$-factorization of $\mu K_{m}$ for every $r \geq 3$ and $m = (2 - C)n$, where $C$ is a constant that depends only on $r$, $\lambda$ and~$\mu$., Comment: 17 pages; fixed the proof of Theorem 1.4 and other minor changes

Let G = (V, E) be an undirected multigraph without loops. The maximum cycle packing problem is to find a collection Z * = {C1, ..., Cs} of edge-disjoint cycles Ci subset G of maximum cardinality v(G). In general, this problem is NP-hard. An approximation algorithm for computing v(G) for 2-connected graphs is presented, which is based on splits of G. It essentially uses the representation of the 3-connected components of G by its SPR-tree. It is proved that for generalized series-parallel multigraphs the algorithm is optimal, i.e. it determines a maximum cycle packing Z * in linear time.

For a loopless multigraph G, the fractional arboricity Arb ( G ) is the maximum of | E ( H ) | | V ( H ) | − 1 over all subgraphs H with at least two vertices. Generalizing the Nash-Williams Arboricity Theorem, the Nine Dragon Tree Conjecture asserts that if Arb ( G ) ≤ k + d k + d + 1 , then G decomposes into k + 1 forests with one having maximum degree at most d. The conjecture was previously proved for d = k + 1 and for k = 1 when d ≤ 6 . We prove it for all d when k ≤ 2 , except for ( k , d ) = ( 2 , 1 ) .

Digraphs are considered by means of eigenvalues of the matrix ?$AA^T$?, and similarly ?$A^T A$?, where ?$A$? is the adjacency matrix of a digraph. The common spectrum of these matrices is called non-negative spectrum or ?$N$?-spectrum of a digraph. Several properties of the ?$N$?-spectrum are proved. The notion of cospectrality is generalized, and some examples of cospectral (multi)(di)graphs are constructed. Digrafe obravnavamo s pomočjo lastnih vrednosti matrike ?$AA^T$?, in podobno ?$A^T A$?, kjer je ?$A$? matrika sosednosti digrafa. Skupni spekter teh matrik se imenuje nenegativni spekter ali ?$N$?-spekter digrafa. Dokažemo več lastnosti ?$N$?-spektra. Posplošimo pojem kospektralnosti in konstruiramo nekaj primerov kospektralnih (multi)(di)grafov.

For d1,s0, a (d,d+s)-graph is a graph whose degrees all lie in the interval {d,d+1,,d+s}. For r1,a0, an (r,r+a)-factor of a graph G is a spanning (r,r+a)-subgraph of G. An (r,r+a)-factorization of a graph G is a decomposition of G into edge-disjoint (r,r+a)-factors. A pseudograph is a graph which may have multiple edges and may have multiple loops. A loop counts two towards the degree of the vertex it is on. A multigraph here has no loops.For t1, let (r,s,a,t) be the least integer such that, if d(r,s,a,t) then every (d,d+s)-pseudograph G has an (r,r+a)-factorization into x(r,r+a)-factors for at least t different values of x. We call (r,s,a,t) the pseudograph(r,s,a,t)-threshold number. Let (r,s,a,t) be the analogous integer for multigraphs. We call (r,s,a,t) the multigraph(r,s,a,t)-threshold number. A simple graph has at most one edge between any two vertices and has no loops. We let (r,s,a,t) be the analogous integer for simple graphs. We call (r,s,a,t) the simple graph(r,s,a,t)-threshold number.In this paper we give the precise value of the pseudograph (r,s,a,t)-threshold number for each value of r,s,a and t. We also use this to give good bounds for the analogous simple graph and multigraph threshold numbers (r,s,a,t) and (r,s,a,t).

DP-coloring (also known as correspondence coloring) is a generalization of list coloring developed recently by Dvořak and Postle. We introduce and study ( i , j ) -defective DP-colorings of multigraphs. We concentrate on sparse multigraphs and consider f D P ( i , j , n ) — the minimum number of edges that may have an n -vertex ( i , j ) -critical multigraph, that is, a multigraph G that has no ( i , j ) -defective DP-coloring but whose every proper subgraph has such a coloring. For every i and j , we find linear lower bounds on f D P ( i , j , n ) that are exact for infinitely many n .

We extend Edmonds’ Branching Theorem to locally finite infinite digraphs. As examples of Oxley or Aharoni and Thomassen show, this cannot be done using ordinary arborescences, whose underlying graphs are trees. Instead we introduce the notion of pseudo-arborescences and prove a corresponding packing result. Finally, we verify some tree-like properties for these objects, but give also an example that their underlying graphs do in general not correspond to topological trees in the Freudenthal compactification of the underlying multigraph of the digraph.

A (finite) graph is odd if all its vertices have odd degrees. The principal aim of this survey is to present the current state of research on covers and decompositions of graphs into fewest possible number of odd subgraphs. Given a graph G , the parameters χ o ′ ( G ) and cov o ( G ) denote, respectively, the minimum size of a decomposition and cover of G consisting of odd subgraphs. Pyber (1991) and Matrai (2006), respectively, have shown that for every simple graph G it holds that χ o ′ ( G ) ≤ 4 and cov o ( G ) ≤ 3 , with both bounds being sharp. The multigraph analogues of the same inequalities, given by the present authors in 2018 and 2019, respectively, are discussed in detail. The list versions of the graph parameters χ o ′ ( G ) and cov o ( G ) , along with other generalizations and possible new directions of related research, are considered in the latter part of the article. Throughout we also pose various structural and algorithmic questions and problems.

Let K n r ; λ 1 , λ 2 be the r -partite multigraph in which each part has size n , where two vertices in the same part or different parts are joined by exactly λ 1 edges or λ 2 edges, respectively. It is proved that there exists a maximal set of t edge-disjoint Hamilton cycles in K n r ; λ 1 , λ 2 for λ 2 n ⌊ r + 3 4 ⌋ ≤ t ≤ m i n { ⌊ λ 2 n 2 ( r − 1 ) 2 ⌋ , ⌊ λ 1 ( n − 1 ) + λ 2 n ( r − 1 ) 2 ⌋ } , the upper bound being best possible. The results proved make use of the method of amalgamations.

We show that any loopy multigraph with a graphical degree sequence can be transformed into a simple graph by a finite sequence of double edge swaps with each swap involving at least one loop or multiple edge. Our result answers a question of Janson motivated by random graph theory, and it adds to the rich literature on reachability of double edge swaps with applications in Markov chain Monte Carlo sampling from the uniform distribution of graphs with prescribed degrees., Comment: 13 pages

Given a proper edge-coloring of a loopless multigraph, the palette of a vertex is defined as the set of colors of the edges which are incident with it. The palette index of a multigraph is defined as the minimum number of distinct palettes occurring among the vertices, taken over all proper edge-colorings of the multigraph itself. In this framework, the palette multigraph of an edge-colored multigraph is defined in this paper and some of its properties are investigated. We show that these properties can be applied in a natural way in order to produce the first known family of multigraphs whose palette index is expressed in terms of the maximum degree by a quadratic polynomial. We also attempt an analysis of our result in connection with some related questions., 13 pages, 2 figures

Staggered quantum walks on graphs are based on the concept of graph tessellation and generalize some well-known discrete-time quantum walk models. In this work, we address the class of 2-tessellable quantum walks with the goal of obtaining an eigenbasis of the evolution operator. By interpreting the evolution operator as a quantum Markov chain on an underlying multigraph, we define the concept of quantum detailed balance, which helps to obtain the eigenbasis. A subset of the eigenvectors is obtained from the eigenvectors of the double discriminant matrix of the quantum Markov chain. To obtain the remaining eigenvectors, we have to use the quantum detailed balance conditions. If the quantum Markov chain has a quantum detailed balance, there is an eigenvector for each fundamental cycle of the underlying multigraph. If the quantum Markov chain does not have a quantum detailed balance, we have to use two fundamental cycles linked by a path in order to find the remaining eigenvectors. We exemplify the process of obtaining the eigenbasis of the evolution operator using the kagome lattice (the line graph of the hexagonal lattice), which has symmetry properties that help in the calculation process., 21 pages, 3 figures

In 1979 Tarsi showed that an edge decomposition of a complete multigraph into stars of size $m$ exists whenever some obvious necessary conditions hold. In 1992 Lonc gave necessary and sufficient conditions for the existence of an edge decomposition of a (simple) complete graph into stars of sizes $m_1,\ldots,m_t$. We show that the general problem of when a complete multigraph admits a decomposition into stars of sizes $m_1,\ldots,m_t$ is $\mathsf{NP}$-complete, but that it becomes tractable if we place a strong enough upper bound on $\max(m_1,\ldots,m_t)$. We determine the upper bound at which this transition occurs. Along the way we also give a characterisation of when an arbitrary multigraph can be decomposed into stars of sizes $m_1,\ldots,m_t$ with specified centres, and a generalisation of Landau's theorem on tournaments., 30 pages, 0 figures

Given a multigraph $G$ and a positive integer $t$, the distance-$t$ chromatic index of $G$ is the least number of colours needed for a colouring of the edges so that every pair of distinct edges connected by a path of fewer than $t$ edges must receive different colours. Let $\pi'_t(d)$ and $\tau'_t(d)$ be the largest values of this parameter over the class of planar multigraphs and of (simple) trees, respectively, of maximum degree $d$. We have that $\pi'_t(d)$ is at most and at least a non-trivial constant multiple larger than $\tau'_t(d)$. (We conjecture $\limsup_{d\to\infty}\pi'_2(d)/\tau'_2(d) =9/4$ in particular.) We prove for odd $t$ the existence of a quantity $g$ depending only on $t$ such that the distance-$t$ chromatic index of any planar multigraph of maximum degree $d$ and girth at least $g$ is at most $\tau'_t(d)$ if $d$ is sufficiently large. Such a quantity does not exist for even $t$. We also show a related, similar phenomenon for distance vertex-colouring., Comment: 16 pages, 1 figure; v2 to appear in Electronic Journal of Combinatorics

A d-dimensional body-hinge framework is a structure consisting of rigid bodies in d-space in which some pairs of bodies are connected by a hinge, restricting the relative position of the corresponding bodies. The framework is said to be globally rigid if every other arrangement of the bodies and their hinges can be obtained by a congruence of the space. The combinatorial structure of a body-hinge framework can be encoded by a multigraph H, in which the vertices correspond to the bodies and the edges correspond to the hinges. We prove that a generic body-hinge realization of a multigraph H is globally rigid in R d , d ? 3 , if and only if ( ( d + 1 2 ) - 1 ) H - e contains ( d + 1 2 ) edge-disjoint spanning trees for all edges e of ( ( d + 1 2 ) - 1 ) H . (For a multigraph H and integer k we use kH to denote the multigraph obtained from H by replacing each edge e of H by k parallel copies of e.) This implies an affirmative answer to a conjecture of Connelly, Whiteley, and the first author.We also consider bar-joint frameworks and show, for each d ? 3 , an infinite family of graphs satisfying Hendrickson's well-known necessary conditions for generic global rigidity in R d (that is, ( d + 1 ) -connectivity and redundant rigidity) which are not generically globally rigid in R d . The existence of these families disproves a number of conjectures, due to Connelly, Connelly and Whiteley, and the third author, respectively.