Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: The neighborhood complex \(\mathcal {N}(G)\) of a graph G was introduced by L. Lovász in his proof of Kneser conjecture. He proved that for any graph G, 2 $$\begin{aligned} \chi (G) \ge conn(\mathcal {N}(G))+3. \end{aligned}$$ In this article we show that for a class of exponential graphs the bound given in (2) is tight. Further, we show that the neighborhood complexes of these exponential graphs are spheres up to homotopy. We were also able to find a class of exponential graphs, which are homotopy test graphs. In 1966, Hedetniemi conjectured that the chromatic number of the categori-cal product of two graphs is the minimum of the chromatic number of the factors. In 2019, Shitov [26] gave a counterexample to this conjecture. Let M(G) denotes the Mycielskian of a graph G. We show that, for any graph G containing \(M(M(K_n))\) as a subgraph and for any graph H, if \(\chi (G \times H) = n+1\) , then \(\min \{\chi (G), \chi (H)\} = n+1\) . Therefore, we enrich the family of graphs satisfying the Hedetniemi’s conjecture. PubDate: 2022-05-13
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: This paper studies an optimization problem of the fashion game on graphs on surfaces, especially on planar graphs. There are rebel players in a graph G. All players choose their actions from an identical set of the two symmetric actions, say \(\{0,1\}\) . An action profile of G is a mapping \(\pi :V(G)\rightarrow \{0,1\}\) . A rebel likes people having the different action with her and dislikes people having the same action. The utility \(u(v,\pi )\) of a player v under the action profile \(\pi\) is the number of neighbors she likes minus the number of neighbors she dislikes. Let \(\phi :V(G)\rightarrow {\mathbb {Z}}\) be a function. The \(\phi\) -satisfiability problem is to determine whether a graph has an action profile under which each player v has a utility at least \(\phi (v)\) . Let t be an integer. The t-satisfiability problem is the specialized \(\phi\) -satisfiability problem when \(\phi (v)=t\) , for each \(v\in V(G)\) . The utility of G, denoted by u(G), is defined to be the maximum t such that G is t-satisfiable. Let \(\eta : V(G)\rightarrow {\mathbb {N}}\) be a function. A mapping \(c:\ V(G)\rightarrow \{0,1\}\) is called an \(\eta\) -defective 2-coloring of G if every \(v\in V(G)\) has at most \(\eta (v)\) neighbors that have the same color with it. For graphs embeddable in surfaces, upper bounds of their utilities are given. The graphs embeddable in the torus or the Klein bottle whose utilities reach their upper bounds are determined. The t-satisfiability problem for graphs embeddable in the plane, the projective plane, the torus, or the Klein bottle is NP-complete if \(t\in \{1,2,3\}\) , and is polynomial time solvable otherwise. We design a dynamic programming algorithm that solves the \(\phi\) -satisfiability problem for outerplanar graphs in \(O( V(G) ^3)\) time. This algorithm can also solve the \(\eta\) -defective 2-coloring problem for outerplanar graphs. PubDate: 2022-05-12
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: We compute the equivariant Euler characteristics of the buildings for the symplectic groups over finite fields. PubDate: 2022-05-11
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: A polynomial is said to be unimodal if its coefficients are non-decreasing and then non-increasing. The domination polynomial of a graph G is the generating function of the number of dominating sets of each cardinality in G, and its coefficients have been conjectured to be unimodal. In this paper we will show the domination polynomial of paths, cycles and complete multipartite graphs are unimodal, and that the domination polynomial of almost every graph is unimodal with mode \( \lceil \frac{n}{2}\rceil \) . PubDate: 2022-05-09
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: In this paper, we classify all commutative weakly distance-regular digraphs of girth g and one type of arcs under the assumption that \(p_{(1,g-1),(1,g-1)}^{(2,g-2)}\ge k_{1,g-1}-2\) . In consequence, Yang et al. (J Comb Theory Ser A 160:288–315, 2018, Theorem 1.1) is partially generalized by our result. PubDate: 2022-05-04
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: The 1-2-3 Conjecture asks whether almost all graphs can be (edge-)labelled with 1, 2, 3 so that no two adjacent vertices are incident to the same sum of labels. In the last decades, several aspects of this problem have been studied in literature, including more general versions and slight variations. Notable such variations include the List 1-2-3 Conjecture variant, in which edges must be assigned labels from dedicated lists of three labels, and the Multiplicative 1-2-3 Conjecture variant, in which labels 1, 2, 3 must be assigned to the edges so that adjacent vertices are incident to different products of labels. Several results obtained towards these two variants led to observe some behaviours that are distant from those of the original conjecture. In this work, we consider the list version of the Multiplicative 1-2-3 Conjecture, proposing the first study dedicated to this very problem. In particular, given any graph G, we wonder about the minimum k such that G can be labelled as desired when its edges must be assigned labels from dedicated lists of size k. Exploiting a relationship between our problem and the List 1-2-3 Conjecture, we provide upper bounds on k when G belongs to particular classes of graphs. We further improve some of these bounds through dedicated arguments. PubDate: 2022-05-04
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract In this paper, we analyze embeddings of grid graphs on orientable surfaces. We determine the genus of two infinite classes of 3-dimensional grid graphs that do not admit quadrilateral embeddings and effective upper bounds for the genus of any 3-dimensional grid graph, both in terms of a grid graph’s combinatorics. As an application, we provide a complete classification of planar and toroidal grid graphs. Our work requires a variety of combinatorial and graph theoretic arguments to determine effective lower bounds on the genus of a grid graph, along with explicitly constructing embeddings of grid graphs on surfaces to determine effective upper bounds on their genera. PubDate: 2022-04-16
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Let \(\lambda \) be a positive integer. An acyclic \(\lambda \) -coloring of a digraph D is a partition of the vertices of D into \(\lambda \) color clases such that the color classes induce acyclic subdigraphs in D. The minimum integer \(\lambda \) for which there exists an acyclic \(\lambda \) -coloring of D is the dichromatic number dc(D) of D. Let \(P(D;\lambda )\) be the dichromatic polynomial of D, which is the number of acyclic \(\lambda \) -colorings of D. In this paper, a recursive formula for \(P(D;\lambda )\) is given. The coefficients of the polynomial \(P(D;\lambda )\) are studied. The dichromatic polynomial of a digraph D is related to the structure of its underlying graph UG(D). Also, we study dichromatic equivalently and dichromatically unique digraphs. PubDate: 2022-04-16
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract We address the problem of constructing large circulant networks with given degree and diameter, and efficient routing schemes. First we discuss the theoretical upper bounds and their asymptotics. Then we apply concepts and tools from the change-making problem to efficient routing in circulant graphs. With these tools we investigate some of the families of circulant graphs that have been proposed in the literature, and we construct tables of large circulant graphs and digraphs with efficient routing properties. PubDate: 2022-04-16
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract A graph is called H-free if it does not contain H as a subgraph. The Turán number of H, denoted by ex(n, H), is the maximum number of edges in any H-free graph on n vertices. For sufficiently large n, Lidický et al. (Electron J Combin 20:62, 2013) determined ex(n, F), where F denotes a class of forest with components each of order 4, and they characterized all the extremal graphs. Moreover, Lan et al. (Appl Math Comput 348: 270–274, 2019) proved that the extremal graph is unique when n is large enough. Motivated by their results, we consider a class of forests F with each component a path or star of order 6, we determine ex(n, F) for sufficiently large n and we also characterize all the extremal graphs. Furthermore, we prove that the extremal graph is unique when n is large enough. Let \(kP_n\) denote the disjoint union of k copies of the path \(P_n\) on n vertices. Recently, Lan et al. (Discuss Math Graph Theory 39: 805–814, 2019) determined the exact value of \(ex(n,2P_7)\) . Motivated by their result, we show that \(ex(n,2P_9) = max\{{(7n+153+r(r-8))/2},7n-27\}\) for all \(n\ge 18\) , where r is the remainder of \(n-17\) when divided by 8. PubDate: 2022-04-15
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Inductive constructions are established for countably infinite simple graphs which have minimally rigid locally generic placements in \({{\mathbb{R}}}^2\) . This generalises a well-known result of Henneberg for generically rigid finite graphs. Inductive methods are also employed in the determination of the infinitesimal flexibility dimension of countably infinite graphs associated with infinitely faceted convex polytopes in \({{\mathbb{R}}}^3\) . In particular, a generalisation of Cauchy’s rigidity theorem is obtained. PubDate: 2022-04-13
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract In this paper, using matrix techniques, we compute the Ihara-zeta function and the number of spanning trees of the join of two semi-regular bipartite graphs. Furthermore, we show that the spectrum and the Ihara-zeta function of the join of two semi-regular bipartite graphs can determine each other. PubDate: 2022-04-07
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Rödl, Ruciński, and Szemerédi determined the minimum \((k-1)\) -degree threshold for the existence of fractional perfect matchings in k-uniform hypergrahs, and Kühn, Osthus, and Townsend extended this result by asymptotically determining the d-degree threshold for the range \(k-1>d\ge k/2\) . In this note, we prove the following exact degree threshold: let k, d be positive integers with \(k\ge 4\) and \(k-1>d\ge k/2\) , and let n be any integer with \(n\ge 2k(k-1)+1\) . Then any n-vertex k-uniform hypergraph with minimum d-degree \(\delta _d(H)>{n-d\atopwithdelims ()k-d} -{n-d-(\lceil n/k\rceil -1)\atopwithdelims ()k-d}\) contains a fractional perfect matching. This lower bound on the minimum d-degree is best possible. We also determine the minimum d-degree threshold for the existence of fractional matchings of size s, where \(0<s\le n/k\) (when \(k/2\le d\le k-1\) ), or with s large enough and \(s\le n/k\) (when \(2k/5<d<k/2\) ). PubDate: 2022-04-06
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract Given a positive integer r, let \([r]=\{1,\ldots ,r\}\) . Let n, m be positive integers such that n is sufficiently large and \(1\le m\le \lfloor n/3\rfloor -1\) . Let H be a 3-graph with vertex set [n], and let \(\delta _1(H)\) denote the minimum vertex degree of H. The size of a maximum matching of H is denoted by \(\nu (H)\) . Kühn, Osthus and Treglown (2013) proved that there exists an integer \(n_0\in \mathbb {N}\) such that if H is a 3-graph with \(n\ge n_0\) vertices and \(\delta _1(H)>{n-1\atopwithdelims ()2}-{n-m\atopwithdelims ()2}\) , then \(\nu (H)\ge m\) . In this paper, we show that there exists an integer \(n_1\in \mathbb {N}\) such that if \( V(H) \ge n_1\) , \(\delta _1(H)>{n-1\atopwithdelims ()2}-{n-m\atopwithdelims ()2}+3\) and \(\nu (H)\le m\) , then H is a subgraph of \(H^*(n,m)\) , where \(H^*(n,m)\) is a 3-graph with vertex set [n] and edge set \(E(H^*(n,m))=\{e\subseteq [n]: e =3 \text{ and } e\cap [m] \ne \emptyset \}\) . The minimum degree condition is best possible. PubDate: 2022-04-06
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract We consider the problem of extending and avoiding partial edge colorings of hypercubes; that is, given a partial edge coloring \(\varphi \) of the d-dimensional hypercube \(Q_d\) , we are interested in whether there is a proper d-edge coloring of \(Q_d\) that agrees with the coloring \(\varphi \) on every edge that is colored under \(\varphi \) ; or, similarly, if there is a proper d-edge coloring that disagrees with \(\varphi \) on every edge that is colored under \(\varphi \) . In particular, we prove that for any \(d\ge 1\) , if \(\varphi \) is a partial d-edge coloring of \(Q_d\) , then \(\varphi \) is avoidable if every color appears on at most d/8 edges and the coloring satisfies a relatively mild structural condition, or \(\varphi \) is proper and every color appears on at most \(d-2\) edges. We also show that \(\varphi \) is avoidable if d is divisible by 3 and every color class of \(\varphi \) is an induced matching. Moreover, for all \(1 \le k \le d\) , we characterize for which configurations consisting of a partial coloring \(\varphi \) of \(d-k\) edges and a partial coloring \(\psi \) of k edges, there is an extension of \(\varphi \) that avoids \(\psi \) . PubDate: 2022-04-04
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract We give a slight improvement on the size of a monochromatic double star we can guarantee in every r-coloring of the edges of \(K_n\) . PubDate: 2022-03-28
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract The connected domination game is played just as the domination game, with an additional requirement that at each stage of the game the vertices played induce a connected subgraph. The number of moves in a D-game (an S-game, resp.) on a graph G when both players play optimally is denoted by \(\gamma _\mathrm{cg}(G)\) ( \(\gamma _\mathrm{cg}'(G)\) , resp.). Connected Game Continuation Principle is established as a substitute for the classical Continuation Principle which does not hold for the connected domination game. Let G x denote the graph G together with a declaration that the vertex x is already dominated. The first main result asserts that if G is a graph with \(\gamma _\mathrm{cg}(G) \ge 3\) and \(x \in V(G)\) , then \(\gamma _\mathrm{cg}(G x) \le 2 \gamma _\mathrm{cg}(G) - 3\) and the bound is sharp. The second main theorem states that if G is a graph with \(n(G) \ge 2\) and \(x \in V(G)\) , then \(\gamma _\mathrm{cg}(G x) \ge \left\lceil \frac{1}{2} \gamma _\mathrm{cg}(G) \right\rceil\) and the bound is sharp. Graphs G and their vertices x for which \(\gamma _\mathrm{cg}'(G x) = \infty\) holds are also characterized. PubDate: 2022-03-25
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract In Henning and Jafari Rad (Graphs Combin, 37: 325–336, 2021), several new probabilistic upper bounds are given on the k-tuple domination number, k-domination number, Roman domination number, and Roman k-domination number of a graph using the well-known Brooks’ Theorem for vertex coloring, improving all of previous given bounds for the above domination variants. In this paper, we use the well-known Turán’s Theorem, and give a slight improvement of all above given bounds. PubDate: 2022-03-23
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: We investigate 2-planarizing 2-factors, i.e. 2-factors of embedded graphs so that cutting along the cycles of the 2-factor we get two plane graphs where the cycles of the 2-factors are a spanning set of face boundaries in each of the graphs. We will give necessary criteria for an abstract graph to have an embedding with a 2-planarizing 2-factor as well as necessary criteria for embedded graphs to have such a 2-factor. Along the way, we discuss to which degree classical results from planar hamiltonicity theory can be extended in our framework. In addition we present computational results on how common 2-planarizing 2-factors are in small cubic graphs. PubDate: 2022-03-23
Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.
Abstract: Abstract In 2012, Henning and Yeo have posed the conjecture that a bipartite 3-regular digraph contains two disjoint cycles of different lengths, and Tan has proved that a 3-regular bipartite digraph, which possesses a cycle factor with at least two cycles, does indeed have two disjoint cycles of different lengths. In this paper, we prove that every 3-regular digraph, which possesses a cycle factor with at least three cycles, contains two disjoint cycles of different lengths, except for the digraph that is isomorphic to the \(D_{2n}^2\) ( \(n\ge 3\) ). PubDate: 2022-03-18
Hybrid journal (It can contain Open Access articles)
[2469 journals]
