Subjects -> MATHEMATICS (Total: 1013 journals)     - APPLIED MATHEMATICS (92 journals)    - GEOMETRY AND TOPOLOGY (23 journals)    - MATHEMATICS (714 journals)    - MATHEMATICS (GENERAL) (45 journals)    - NUMERICAL ANALYSIS (26 journals)    - PROBABILITIES AND MATH STATISTICS (113 journals) MATHEMATICS (714 journals)                  1 2 3 4 | Last

1 2 3 4 | Last

Similar Journals
 Discussiones Mathematicae Graph TheoryJournal Prestige (SJR): 0.633 Citation Impact (citeScore): 1Number of Followers: 1     Open Access journal ISSN (Print) 1234-3099 - ISSN (Online) 2083-5892 Published by Sciendo  [370 journals]
• On the Equality of Domination Number and 2-Domination Number

• Abstract: The 2-domination number γ2(G) of a graph G is the minimum cardinality of a set D ⊆ V (G) for which every vertex outside D is adjacent to at least two vertices in D. Clearly, γ2(G) cannot be smaller than the domination number γ(G). We consider a large class of graphs and characterize those members which satisfy γ2 = γ. For the general case, we prove that it is NP-hard to decide whether γ2 = γ holds. We also give a necessary and sufficient condition for a graph to satisfy the equality hereditarily.
PubDate: Tue, 22 Mar 2022 00:00:00 GMT

• Edge Degree Conditions for Dominating and Spanning Closed Trails

• Abstract: Edge degree conditions have been studied since the 1980s, mostly with regard to hamiltonicity of line graphs and the equivalent existence of dominating closed trails in their root graphs, as well as the stronger property of being supereulerian, i.e., admitting a spanning closed trail. For a graph G, let σ¯2(G)=min{ d(u)+d(v) uv∈E(G) }{\bar \sigma _2}\left( G \right) = \min \left\{ {d\left( u \right) + d\left( v \right) uv \in E\left( G \right)} \right\}. Chen et al. conjectured that a 3-edge-connected graph G with sufficientl large order n and σ¯2(G)>n9-2{\bar \sigma _2}\left( G \right) > {n \over 9} - 2 is either supereulerian or contractible to the Petersen graph. We show that the conjecture is true when σ¯2(G)≥2(⌊ n/15 ⌋−1){\bar \sigma _2}\left( G \right) \ge 2\left( {\left\lfloor {n/15} \right\rfloor - 1} \right). Furthermore, we show that for an essentially k-edge-connected graph G with sufficiently large order n, the following statements hold.(i) If k = 2 and σ¯2(G)≥2(⌊ n/8 ⌋−1){\bar \sigma _2}\left( G \right) \ge 2\left( {\left\lfloor {n/8} \right\rfloor - 1} \right), then either L(G) is hamiltonian or G can be contracted to one of a set of six graphs which are not supereulerian;(ii) If k = 3 and σ¯2(G)≥2(⌊ n/15 ⌋−1){\bar \sigma _2}\left( G \right) \ge 2\left( {\left\lfloor {n/15} \right\rfloor - 1} \right), then either L(G) is hamiltonian or G can be contracted to the Petersen graph.
PubDate: Tue, 22 Mar 2022 00:00:00 GMT

• The Achromatic Number of the Cartesian Product of and

• Abstract: Let G be a graph and C a finite set of colours. A vertex colouring f : V (G) → C is complete if for any pair of distinct colours c1, c2 ∈ C one can find an edge {v1, v2} ∈ E(G) such that f(vi) = ci, i = 1, 2. The achromatic number of G is defined to be the maximum number achr(G) of colours in a proper complete vertex colouring of G. In the paper achr(K6 □ Kq) is determined for any integer q such that either 8 ≤ q ≤ 40 or q ≥ 42 is even.
PubDate: Tue, 22 Mar 2022 00:00:00 GMT

• Chorded -Pancyclic and Weakly -Pancyclic Graphs

• Abstract: As natural relaxations of pancyclic graphs, we say a graph G is kpancyclic if G contains cycles of each length from k to V (G) and G is weakly pancyclic if it contains cycles of all lengths from the girth to the circumference of G, while G is weakly k-pancyclic if it contains cycles of all lengths from k to the circumference of G. A cycle C is chorded if there is an edge between two vertices of the cycle that is not an edge of the cycle. Combining these ideas, a graph is chorded pancyclic if it contains chorded cycles of each length from 4 to the circumference of the graph, while G is chorded k-pancyclic if there is a chorded cycle of each length from k to V (G) . Further, G is chorded weakly k-pancyclic if there is a chorded cycle of each length from k to the circumference of the graph. We consider conditions for graphs to be chorded weakly k-pancyclic and chorded k-pancyclic.
PubDate: Fri, 18 Feb 2022 00:00:00 GMT

• On -Hamiltonian-Connected Line Graphs

• Abstract: For an integer s ≥ 0, G is s-hamiltonian-connected if for any vertex subset S ⊆ V (G) with S ≤ s, G − S is hamiltonian-connected. Thomassen in 1984 conjectured that every 4-connected line graph is hamiltonian (see [Reflections on graph theory, J. Graph Theory 10 (1986) 309–324]), and Kužel and Xiong in 2004 conjectured that every 4-connected line graph is hamiltonian-connected (see [Z. Ryjáček and P. Vrána, Line graphs of multigraphs and Hamilton-connectedness of claw-free graphs, J. Graph Theory 66 (2011) 152–173]). In this paper we prove the following. (i) For s ≥ 3, every (s + 4)-connected line graph is s-hamiltonian-connected. (ii) For s ≥ 0, every (s + 4)-connected line graph of a claw-free graph is s-hamiltonian-connected.
PubDate: Fri, 18 Feb 2022 00:00:00 GMT

• Cubic Graphs Having Only -Cycles in Each 2-Factor

• Abstract: We consider the class of 2-connected cubic graphs having only k-cycles in each 2-factor, and obtain the following two results: (i) every 2-connected cubic graph having only 8-cycles in each 2-factor is isomorphic to a unique Hamiltonian graph of order 8; and (ii) a 2-connected cubic planar graph G has only k-cycles in each 2-factor if and only if k = 4 and G is the complete graph of order 4.
PubDate: Fri, 18 Feb 2022 00:00:00 GMT

• Describing Neighborhoods of 5-Vertices in 3-Polytopes with Minimum Degree
5 and Without Vertices of Degrees from 7 to 11

• Abstract: In 1940, Lebesgue proved that every 3-polytope contains a 5-vertex for which the set of degrees of its neighbors is majorized by one of the following sequences:(6, 6, 7, 7, 7), (6, 6, 6, 7, 9), (6, 6, 6, 6, 11), (5, 6, 7, 7, 8), (5, 6, 6, 7, 12), (5, 6, 6, 8, 10), (5, 6, 6, 6, 17), (5, 5, 7, 7, 13), (5, 5, 7, 8, 10), (5, 5, 6, 7, 27), (5, 5, 6, 6, ∞), (5, 5, 6, 8, 15), (5, 5, 6, 9, 11), (5, 5, 5, 7, 41), (5, 5, 5, 8, 23), (5, 5, 5, 9, 17), (5, 5, 5, 10, 14), (5, 5, 5, 11, 13). In this paper we prove that every 3-polytope without vertices of degree from 7 to 11 contains a 5-vertex for which the set of degrees of its neighbors is majorized by one of the following sequences: (5, 5, 6, 6, ∞), (5, 6, 6, 6, 15), (6, 6, 6, 6, 6), where all parameters are tight.
PubDate: Tue, 19 Jun 2018 00:00:00 GMT

• Equitable Coloring and Equitable Choosability of Graphs with Small Maximum
Average Degree

• Abstract: A graph is said to be equitably k-colorable if the vertex set V (G) can be partitioned into k independent subsets V1, V2, . . . , Vk such that Vi − Vj ≤ 1 (1 ≤ i, j ≤ k). A graph G is equitably k-choosable if, for any given k-uniform list assignment L, G is L-colorable and each color appears on at most ⌈ V(G) k⌉$\left\lceil {{{\left {V(G)} \right } \over k}} \right\rceil$ vertices. In this paper, we prove that if G is a graph such that mad(G) < 3, then G is equitably k-colorable and equitably k- choosable where k ≥ max{Δ(G), 4}. Moreover, if G is a graph such that 125${{12} \over 5}$, then G is equitably k-colorable and equitably k-choosable where k ≥ max{Δ (G), 3}.
PubDate: Tue, 19 Jun 2018 00:00:00 GMT

• The {−2,−1}-Selfdual and Decomposable Tournaments

• Abstract: We only consider finite tournaments. The dual of a tournament is obtained by reversing all the arcs. A tournament is selfdual if it is isomorphic to its dual. Given a tournament T, a subset X of V (T) is a module of T if each vertex outside X dominates all the elements of X or is dominated by all the elements of X. A tournament T is decomposable if it admits a module X such that 1 < X < V (T) .We characterize the decomposable tournaments whose subtournaments obtained by removing one or two vertices are selfdual. We deduce the following result. Let T be a non decomposable tournament. If the subtournaments of T obtained by removing two or three vertices are selfdual, then the subtournaments of T obtained by removing a single vertex are not decomposable. Lastly, we provide two applications to tournaments reconstruction.
PubDate: Tue, 19 Jun 2018 00:00:00 GMT

• Completely Independent Spanning Trees in -Th Power of Graphs

• Abstract: Let T1, T2, . . . , Tk be spanning trees of a graph G. For any two vertices u, v of G, if the paths from u to v in these k trees are pairwise openly disjoint, then we say that T1, T2, . . . , Tk are completely independent. Araki showed that the square of a 2-connected graph G on n vertices with n ≥ 4 has two completely independent spanning trees. In this paper, we prove that the k-th power of a k-connected graph G on n vertices with n ≥ 2k has k completely independent spanning trees. In fact, we prove a stronger result: if G is a connected graph on n vertices with δ(G) ≥ k and n ≥ 2k, then the k-th power Gk of G has k completely independent spanning trees.
PubDate: Tue, 19 Jun 2018 00:00:00 GMT

• Reconfiguring Minimum Dominating Sets: The γ-Graph of a Tree

• Abstract: We consider γ-graphs, which are reconfiguration graphs of the minimum dominating sets of a graph G. We answer three open questions about γ- graphs of trees by providing upper bounds on the maximum degree, the diameter, and the number of minimum dominating sets. The latter gives an upper bound on the order of the γ-graph.
PubDate: Tue, 19 Jun 2018 00:00:00 GMT

• Hamiltonian and Pancyclic Graphs in the Class of Self-Centered Graphs with

• Abstract: The paper deals with Hamiltonian and pancyclic graphs in the class of all self-centered graphs of radius 2. For both of the two considered classes of graphs we have done the following. For a given number n of vertices, we have found an upper bound of the minimum size of such graphs. For n ≤ 12 we have found the exact values of the minimum size. On the other hand, the exact value of the maximum size has been found for every n. Moreover, we have shown that such a graph (of order n and) of size m exists for every m between the minimum and the maximum size. For n ≤ 10 we have found all nonisomorphic graphs of the minimum size, and for n = 11 only for Hamiltonian graphs.
PubDate: Tue, 19 Jun 2018 00:00:00 GMT

• A Note on the Thue Chromatic Number of Lexicographic Products of Graphs

• Abstract: A sequence is called non-repetitive if none of its subsequences forms a repetition (a sequence r1r2⋯r2n such that ri = rn+i for all 1 ≤ i ≤ n). Let G be a graph whose vertices are coloured. A colouring ϕ of the graph G is non-repetitive if the sequence of colours on every path in G is non-repetitive. The Thue chromatic number, denoted by π(G), is the minimum number of colours of a non-repetitive colouring of G.In this short note we present two general upper bounds for the Thue chromatic number for the lexicographic product G ◦ H of graphs G and H with respect to some properties of the factors. One upper bound is then used to derive the exact values for π(G ◦ H) when G is a complete multipartite graph and H an arbitrary graph.
PubDate: Tue, 19 Jun 2018 00:00:00 GMT

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