On the unitary Cayley graph of a finite ring.
On the upper and lower chromatic numbers of BSQSs(16).
On the upper bounds for the first Zagreb index
On the vertex connectivity of a relation in an association scheme.
On the Vertex Folkman Numbers Fv(2,...,2;q)
2000 Mathematics Subject Classification: 05C55.In this paper we shall compute the Folkman numbers ... We prove also new bounds for some vertex and edge Folkman numbers.
On the Vertex Separation of Cactus Graphs
This paper is part of a work in progress whose goal is to construct a fast, practical algorithm for the vertex separation (VS) of cactus graphs. We prove a theorem for cacti", a necessary and sufficient condition for the VS of a cactus graph being k. Further, we investigate the ensuing ramifications that prevent the construction of an algorithm based on that theorem only.
On the Vertex Separation of Maximal Outerplanar Graphs
We investigate the NP-complete problem Vertex Separation (VS) on Maximal Outerplanar Graphs (mops). We formulate and prove a “main theorem for mops”, a necessary and sufficient condition for the vertex separation of a mop being k. The main theorem reduces the vertex separation of mops to a special kind of stretchability, one that we call affixability, of submops.
On the volume of a certain polytope.
On the volume of the polytope of doubly stochastic matrices.
On the Weight of Minor Faces in Triangle-Free 3-Polytopes
The weight w(f) of a face f in a 3-polytope is the degree-sum of vertices incident with f. It follows from Lebesgue’s results of 1940 that every triangle-free 3-polytope without 4-faces incident with at least three 3-vertices has a 4-face with w ≤ 21 or a 5-face with w ≤ 17. Here, the bound 17 is sharp, but it was still unknown whether 21 is sharp. The purpose of this paper is to improve this 21 to 20, which is best possible.
On the Zagreb index of quasi-tree graphs.
On theH-Force Number of Hamiltonian Graphs and Cycle Extendability
The H-force number h(G) of a hamiltonian graph G is the smallest cardinality of a set A ⊆ V (G) such that each cycle containing all vertices of A is hamiltonian. In this paper a lower and an upper bound of h(G) is given. Such graphs, for which h(G) assumes the lower bound are characterized by a cycle extendability property. The H-force number of hamiltonian graphs which are exactly 2-connected can be calculated by a decomposition formula.
On Thom Polynomials for A4(−) via Schur Functions
2000 Mathematics Subject Classification: 05E05, 14N10, 57R45.We study the structure of the Thom polynomials for A4(−) singularities. We analyze the Schur function expansions of these polynomials. We show that partitions indexing the Schur function expansions of Thom polynomials for A4(−) singularities have at most four parts. We simplify the system of equations that determines these polynomials and give a recursive description of Thom polynomials for A4(−) singularities. We also give Thom polynomials...
On Tits' conjecture and other questions concerning Artin and generalized Artin groups.
On total matching numbers and total covering numbers for -uniform hypergraphs
On total restrained domination in graphs
In this paper we initiate the study of total restrained domination in graphs. Let be a graph. A total restrained dominating set is a set where every vertex in is adjacent to a vertex in as well as to another vertex in , and every vertex in is adjacent to another vertex in . The total restrained domination number of , denoted by , is the smallest cardinality of a total restrained dominating set of . First, some exact values and sharp bounds for are given in Section 2. Then the Nordhaus-Gaddum-type...
On total vertex irregularity strength of graphs
Martin Bača et al. [2] introduced the problem of determining the total vertex irregularity strengths of graphs. In this paper we discuss how the addition of new edge affect the total vertex irregularity strength.
On tours that contain all edges of a hypergraph.
On traceability and 2-factors in claw-free graphs
If G is a claw-free graph of sufficiently large order n, satisfying a degree condition σₖ > n + k² - 4k + 7 (where k is an arbitrary constant), then G has a 2-factor with at most k - 1 components. As a second main result, we present classes of graphs ₁,...,₈ such that every sufficiently large connected claw-free graph satisfying degree condition σ₆(k) > n + 19 (or, as a corollary, δ(G) > (n+19)/6) either belongs to or is traceable.
On transitive orientations of G-ê
A comparability graph is a graph whose edges can be oriented transitively. Given a comparability graph G = (V,E) and an arbitrary edge ê∈ E we explore the question whether the graph G-ê, obtained by removing the undirected edge ê, is a comparability graph as well. We define a new substructure of implication classes and present a complete mathematical characterization of all those edges.