Subjects -> ENGINEERING (Total: 2688 journals)     - CHEMICAL ENGINEERING (229 journals)    - CIVIL ENGINEERING (237 journals)    - ELECTRICAL ENGINEERING (176 journals)    - ENGINEERING (1325 journals)    - ENGINEERING MECHANICS AND MATERIALS (452 journals)    - HYDRAULIC ENGINEERING (56 journals)    - INDUSTRIAL ENGINEERING (98 journals)    - MECHANICAL ENGINEERING (115 journals) ENGINEERING (1325 journals)                  1 2 3 4 5 6 7 | Last
Similar Journals
 Graphs and CombinatoricsJournal Prestige (SJR): 0.728 Citation Impact (citeScore): 1Number of Followers: 4      Hybrid journal (It can contain Open Access articles) ISSN (Print) 1435-5914 - ISSN (Online) 0911-0119 Published by Springer-Verlag  [2469 journals]
• Neighborhood Complexes, Homotopy Test Graphs and an Application to
Coloring of Product Graphs

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

• Fashion Game on Planar Graphs

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

• Equivariant Euler Characteristics of Symplectic Buildings

Abstract: We compute the equivariant Euler characteristics of the buildings for the symplectic groups over finite fields.
PubDate: 2022-05-11

• On the Unimodality of Domination Polynomials

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

• Weakly Distance-Regular Digraphs of One Type of Arcs

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

• On a List Variant of the Multiplicative 1-2-3 Conjecture

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

• Embedding Grid Graphs on Surfaces

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

• The Dichromatic Polynomial of a Digraph

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

• Greedy Routing in Circulant Networks

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

• The Turán Numbers of Special Forests

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

• The Rigidity of Infinite Graphs II

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

• The Ihara-Zeta Function and the Spectrum of the Join of Two Semi-Regular
Bipartite Graphs

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

• A Note on Exact Minimum Degree Threshold for Fractional Perfect Matchings

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

• Stability on Matchings in 3-Uniform Hypergraphs

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

• Avoiding and Extending Partial Edge Colorings of Hypercubes

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

• Improved Monochromatic Double Stars in Edge Colorings

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

• Predominating a Vertex in the Connected Domination Game

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

• Improved Bounds on the k-tuple (Roman) Domination Number of a Graph

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

• On 2-Factors Splitting an Embedded Graph into Two Plane Graphs

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

• Disjoint Cycles of Different Lengths in 3-Regular Digraphs

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

JournalTOCs
School of Mathematical and Computer Sciences
Heriot-Watt University
Edinburgh, EH14 4AS, UK
Email: journaltocs@hw.ac.uk
Tel: +00 44 (0)131 4513762