1,380 results
Search Results
2. Not-all-equal 3-SAT and 2-colorings of 4-regular 4-uniform hypergraphs.
- Author
-
Henning, Michael A. and Yeo, Anders
- Subjects
- *
HYPERGRAPHS , *GRAPH theory , *GEOMETRIC vertices , *MATHEMATICS , *GEOMETRY - Abstract
In this paper, we continue our study of 2-colorings in hypergraphs (see, Henning and Yeo, 2013). A hypergraph is 2-colorable if there is a 2-coloring of the vertices with no monochromatic hyperedge. It is known (see Thomassen, 1992) that every 4-uniform 4-regular hypergraph is 2-colorable. Our main result in this paper is a strengthening of this result. For this purpose, we define a vertex in a hypergraph H to be a free vertex in H if we can 2-color V ( H ) ∖ { v } such that every hyperedge in H contains vertices of both colors (where v has no color). We prove that every 4-uniform 4-regular hypergraph has a free vertex. This proves a conjecture in Henning and Yeo (2015). Our proofs use a new result on not-all-equal 3-SAT which is also proved in this paper and is of interest in its own right. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
3. Activation strategy for relaxed asymmetric coloring games
- Author
-
Yang, Daqing
- Subjects
- *
GRAPH coloring , *TREE graphs , *COMPUTATIONAL mathematics , *FINITE geometries , *MATHEMATICS - Abstract
Abstract: This paper investigates a competitive version of the coloring game on a finite graph . An asymmetric variant of the -relaxed coloring game is called the -relaxed -coloring game. In this game, two players, Alice and Bob, take turns coloring the vertices of a graph , using colors from a set , with . On each turn Alice colors vertices and Bob colors vertices. A color is legal for an uncolored vertex if by coloring with color , the subgraph induced by all the vertices colored with has maximum degree at most . Each player is required to color an uncolored vertex legally on each move. The game ends when there are no remaining uncolored vertices. Alice wins the game if all vertices of the graph are legally colored, Bob wins if at a certain stage there exists an uncolored vertex without a legal color. The -relaxed -game chromatic number of , denoted -, is the least for which Alice has a winning strategy in the -relaxed -coloring game. This paper extends the well-studied activation strategy of coloring games to relaxed asymmetric coloring games. The extended strategy is then applied to the -relaxed -coloring games on planar graphs, partial -trees and -pseudo-partial -trees. This paper shows that for planar graphs , if , then - for all . If is a partial -tree, , then - for all . If is an -pseudo-partial -tree, , let , then - for all . For planar graphs and , - for all . These results extend the corresponding -relaxed -coloring game results to more generalized asymmetric cases. [Copyright &y& Elsevier]
- Published
- 2009
- Full Text
- View/download PDF
4. Relaxed very asymmetric coloring games
- Author
-
Yang, Daqing
- Subjects
- *
GRAPH coloring , *GRAPH theory , *MATHEMATICAL analysis , *MATHEMATICS , *COMBINATORICS , *ALGEBRA - Abstract
Abstract: This paper investigates a competitive version of the coloring game on a finite graph . An asymmetric variant of the -relaxed coloring game is called the -relaxed -coloring game. In this game, two players, Alice and Bob, take turns coloring the vertices of a graph , using colors from a set , with . On each turn Alice colors vertices and Bob colors vertices. A color is legal for an uncolored vertex if by coloring with color , the subgraph induced by all the vertices colored with has maximum degree at most . Each player is required to color an uncolored vertex legally on each move. The game ends when there are no remaining uncolored vertices. Alice wins the game if all vertices of the graph are legally colored, Bob wins if at a certain stage there exists an uncolored vertex without a legal color. The -relaxed -game chromatic number, denoted by , of is the least for which Alice has a winning strategy in the -relaxed -coloring game. The -relaxed -coloring game has been well studied and there are many interesting results. For the -relaxed -coloring game, this paper proves that if a graph has an orientation with maximum outdegree and , then for all ; If , then - for all . [Copyright &y& Elsevier]
- Published
- 2009
- Full Text
- View/download PDF
5. On 2-factors with cycles containing specified edges in a bipartite graph
- Author
-
Yan, Jin and Liu, Guizhen
- Subjects
- *
FACTORS (Algebra) , *BIPARTITE graphs , *QUADRILATERALS , *MATHEMATICAL analysis , *GRAPH theory , *MATHEMATICS - Abstract
Abstract: Let be an integer and a bipartite graph with such that . In this paper it has been proved that if for each pair of nonadjacent vertices and , , then for any independent edges of , has a 2-factor with cycles such that and for each . We shall also show that the conditions in this paper are sharp. [Copyright &y& Elsevier]
- Published
- 2009
- Full Text
- View/download PDF
6. Semisymmetric graphs
- Author
-
Feng, Yan-Quan and Zhou, Jin-Xin
- Subjects
- *
GRAPH theory , *MATHEMATICS , *MATHEMATICAL transformations , *ISOMORPHISM (Mathematics) - Abstract
Abstract: Let be a regular covering projection of connected graphs with the group of covering transformations isomorphic to N. If N is an elementary abelian p-group, then the projection is called p-elementary abelian. The projection is vertex-transitive (edge-transitive) if some vertex-transitive (edge-transitive) subgroup of the automorphism group of X lifts along , and semisymmetric if it is edge- but not vertex-transitive. The projection is minimal semisymmetric if it cannot be written as a composition of two (nontrivial) regular covering projections, where is semisymmetric. Malnič et al. [Semisymmetric elementary abelian covers of the Möbius–Kantor graph, Discrete Math. 307 (2007) 2156–2175] determined all pairwise nonisomorphic minimal semisymmetric elementary abelian regular covering projections of the Möbius–Kantor graph, the Generalized Petersen graph , by explicitly giving the corresponding voltage rules generating the covering projections. It was remarked at the end of the above paper that the covering graphs arising from these covering projections need not themselves be semisymmetric (a graph with regular valency is said to be semisymmetric if its automorphism group is edge- but not vertex-transitive). In this paper it is shown that all these covering graphs are indeed semisymmetric. [Copyright &y& Elsevier]
- Published
- 2008
- Full Text
- View/download PDF
7. A conjecture on the reconstruction of graphs from metric balls of their vertices
- Author
-
Levenshtein, Vladimir I.
- Subjects
- *
RECONSTRUCTION (U.S. history, 1865-1877) , *RADIAL bone , *MAXIMA & minima , *MATHEMATICS - Abstract
Abstract: In this paper we investigate a new graph reconstruction problem which was introduced in a paper by Levenshtein, Konstantinova, Konstantinov and Molodtsov [Reconstruction of a graph from 2-vicinities of its vertices, Discrete Appl. Math., accepted for publication], motivated by reconstruction of chemical compounds. It consists of the exact reconstruction of an unknown simple connected graph G from subsets of vertices which are metric balls of radius r () around all its vertices. A metric ball of radius r about vertex is the set of all vertices of distance at most r from . The value is introduced which is equal to the minimum number t such that a simple connected graph G without terminal vertices with girth at least t is reconstructible from metric balls of radius r around all its vertices. Consideration of the cycle graph with vertices shows that . We conjecture that . The main result is the upper bound which, in particular, implies that this conjecture is true for . Moreover, it is proved that if the knowledge of metric balls of radius r around all vertices of a simple connected graph G without terminal vertices with girth at least allows one to determine at least one edge of G. [Copyright &y& Elsevier]
- Published
- 2008
- Full Text
- View/download PDF
8. Graphs encoding 3-manifolds of genus 2
- Author
-
Cavicchioli, Alberto and Spaggiari, Fulvia
- Subjects
- *
MATHEMATICS , *GRAPHIC methods , *GEOMETRY , *GEOMETRICAL drawing - Abstract
Abstract: We give a simple alternative proof of the representation theorem of all genus two 3-manifolds by a 6-parameter family of integers, due to Casali and Grasselli (see [M.R. Casali, A catalogue of the genus two 3-manifolds, Atti. Sem. Mat. Fis. Univ. Modena 37 (1989) 207–236]; [M.R. Casali, L. Grasselli, 2-Symmetric crystallizations and 2-fold branched coverings of , Discrete Math. 87 (1991) 9–22]). Our approach is different from that of the quoted papers, and it is based on the concept of extended Heegaard diagram. This permits to obtain new topological meanings of the arithmetic conditions which the parameters must satisfy for representing closed manifolds. Some applications and results on some homology spheres of genus 2 complete the paper. [Copyright &y& Elsevier]
- Published
- 2008
- Full Text
- View/download PDF
9. On the topology of the free complexes of convex geometries
- Author
-
Hachimori, Masahiro and Kashiwabara, Kenji
- Subjects
- *
GEOMETRY , *MATHEMATICS , *LINEAR algebra , *MATHEMATICAL analysis - Abstract
Abstract: We investigate the free complex of a convex geometry. Edelman and Reiner showed that the free complex of a convex geometry is contractible. Moreover, their paper stated a conjecture about the topology of free complexes. This paper proves their conjecture. [Copyright &y& Elsevier]
- Published
- 2007
- Full Text
- View/download PDF
10. On the direct limit of a direct system of multialgebras
- Author
-
Pelea, Cosmin
- Subjects
- *
MATHEMATICS , *ALGEBRA , *UNIVERSAL algebra , *COMPLEX numbers - Abstract
Abstract: This paper deals with multialgebras. An important tool in the theory of multialgebras is the fundamental relation, which brings us into the class of the universal algebras. In this paper we will present the construction of the direct limit of a direct system of multialgebras, some basic properties of this construction, and we will see that the fundamental algebra of the direct limit of multialgebras is the direct limit of the fundamental algebras of the given multialgebras. [Copyright &y& Elsevier]
- Published
- 2006
- Full Text
- View/download PDF
11. Packing two copies of a tree into its third power
- Author
-
Kaneko, Atsushi and Suzuki, Kazuhiro
- Subjects
- *
GRAPH theory , *CHARTS, diagrams, etc. , *GRAPHIC methods , *MATHEMATICS - Abstract
Abstract: A graph H of order n is said to be k-placeable into a graph G of order n, if G contains k edge-disjoint copies of H. It is well known that any non-star tree T of order n is 2-placeable into the complete graph . In the paper by Kheddouci et al. [Packing two copies of a tree into its fourth power, Discrete Math. 213 (2000) 169–178], it is proved that any non-star tree T is 2-placeable into . In this paper, we prove that any non-star tree T is 2-placeable into . [Copyright &y& Elsevier]
- Published
- 2006
- Full Text
- View/download PDF
12. A hierarchy of randomness for graphs
- Author
-
Simonovits, Miklós and Sós, Vera T.
- Subjects
- *
RANDOM graphs , *GRAPH theory , *MATHEMATICS , *ALGEBRA - Abstract
Abstract: In this paper we formulate four families of problems with which we aim at distinguishing different levels of randomness. The first one is completely non-random, being the ordinary Ramsey–Turán problem and in the subsequent three problems we formulate some randomized variations of it. As we will show, these four levels form a hierarchy. In a continuation of this paper we shall prove some further theorems and discuss some further, related problems. [Copyright &y& Elsevier]
- Published
- 2005
- Full Text
- View/download PDF
13. -algebra of fractions and maximal -algebra of fractions
- Author
-
Buşneag, Dumitru and Chirteş, Florentina
- Subjects
- *
ALGEBRA , *FRACTIONS , *MATHEMATICAL analysis , *MATHEMATICS - Abstract
Abstract: The aim of this paper is to define the notions of -valued Lukasiewicz-Moisil algebra of fractions and maximal algebra of fractions taking as a guide-line the elegant construction of a complete ring of fractions by partial morphisms introduced by [Lambek, 1996. Lectures on Rings and Modules, p. 36]. For some informal explanations of the notion of fraction see [Lambek, 1996. Lectures on Rings and Modules, p. 36] In the last part of this paper we prove the existence of a maximal n-valued Lukasiewicz–Moisil algebra of fractions for an n-valued Lukasiewicz–Moisil algebra (Theorem 3.2) and we give an explicit description of this -valued Lukasiewicz–Moisil algebra for some classes of -valued Lukasiewicz–Moisil algebras (finite, chains, Boolean algebras). [Copyright &y& Elsevier]
- Published
- 2005
- Full Text
- View/download PDF
14. Steiner trade spectra of complete partite graphs
- Author
-
Lefevre, James G.
- Subjects
- *
DISCRETE mathematics , *MATHEMATICS , *INTERFEROMETRY , *SPECTRUM analysis - Abstract
Abstract: The Steiner trade spectrum of a simple graph G is the set of all integers t for which there is a simple graph H whose edges can be partitioned into t copies of G in two entirely different ways. The Steiner trade spectra of complete partite graphs were determined in all but a few cases in a recent paper by Billington and Hoffman (Discrete Math. 250 (2002) 23). In this paper we resolve the remaining cases. [Copyright &y& Elsevier]
- Published
- 2004
- Full Text
- View/download PDF
15. Eccentric digraphs
- Author
-
Boland, James, Buckley, Fred, and Miller, Mirka
- Subjects
- *
DIRECTED graphs , *MATHEMATICAL analysis , *GRAPH theory , *MATHEMATICS - Abstract
The distance
d(u,v) from vertexu to vertexv in a digraphG is the length of the shortest directed path fromu tov . The eccentricitye(v) of vertexv is the maximum distance ofv to any other vertex ofG . A vertexu is an eccentric vertex of vertexv if the distance fromv tou is equal to the eccentricity ofv . The eccentric digraphED(G) of a digraphG is the digraph that has the same vertex set asG and the arc set defined by: there is an arc fromu tov iffv is an eccentric vertex ofu . The idea of the eccentric digraph of a graph was introduced by Buckley (Congr. Numer. 149 (2001) 65) and the idea of the eccentric digraph of a digraph by Boland and Miller (Proceedings of AWOCA’01, July 2001, p. 66). In this paper, we examine eccentric digraphs of digraphs for various families of digraphs and we consider the behaviour of an iterated sequence of eccentric digraphs of a digraph. The paper concludes with several open problems. [Copyright &y& Elsevier]- Published
- 2004
- Full Text
- View/download PDF
16. On subgraphs of Cartesian product graphs and S-primeness
- Author
-
Brešar, Boštjan
- Subjects
- *
GRAPHIC methods , *AGNATHA , *MATHEMATICS - Abstract
In this paper we consider S-prime graphs, that is the graphs that cannot be represented as nontrivial subgraphs of nontrivial Cartesian products of graphs. Lamprey and Barnes characterized S-prime graphs via so-called basic S-prime graphs that form a subclass of all S-prime graphs. However, the structure of basic S-prime graphs was not known very well. In this paper we prove several characterizations of basic S-prime graphs. In particular, the structural characterization of basic S-prime graphs of connectivity
2 enables us to present several infinite families of basic S-prime graphs. Furthermore, simple S-prime graphs are introduced that form a relatively small subclass of basic S-prime graphs, and it is shown that every basic S-prime graph can be obtained from a simple S-prime graph by a sequence of certain transformations called extensions. [Copyright &y& Elsevier]- Published
- 2004
- Full Text
- View/download PDF
17. Problems and results in extremal combinatorics—I
- Author
-
Alon, Noga
- Subjects
- *
COMBINATORICS , *MATHEMATICS , *GEOMETRY , *GRAPH theory - Abstract
Extremal combinatorics is an area in discrete mathematics that has developed spectacularly during the last decades. This paper contains a collection of problems and results in the area, including solutions or partial solutions to open problems suggested by various researchers in extremal graph theory, extremal finite set theory and combinatorial geometry. This is not meant to be a comprehensive survey of the area, it is merely a collection of various extremal problems, which are hopefully interesting. The choice of the problems is inevitably somewhat biased, and as the title of the paper suggests I hope to write a related paper in the future. Each section of this paper is essentially self contained, and can be read separately. [Copyright &y& Elsevier]
- Published
- 2003
- Full Text
- View/download PDF
18. Infinite families of crossing-critical graphs with given average degree
- Author
-
Salazar, Gelasio
- Subjects
- *
GRAPHIC methods , *RATIONAL numbers , *MATHEMATICS - Abstract
In their paper on minimal graphs with crossing number at least
k (or, equivalently,k -crossing-critical graphs) (J. Combin. Theory Ser. B 58 (2) (1993) 217–224) Richter and Thomassen described a construction of an infinite family of 4-regular 3-crossing-critical graphs. They also showed that no infinite family of 6-regulark -crossing-critical graphs exists. In this paper we generalize the Richter and Thomassen construction, and prove the following result: for each rational numberq∈[4,6) there is an infinite family of graphs that arek -crossing-critical for the same integerk , each of which has average degreeq . Moreover, we show that for each rational numberq∈[4,6) this statement holds for infinitely many values ofk . [Copyright &y& Elsevier]- Published
- 2003
- Full Text
- View/download PDF
19. Non-repetitive colorings of infinite sets
- Author
-
Grytczuk, Jaroslaw and Śliwa, Wieslaw
- Subjects
- *
COLORING matter , *MATHEMATICAL sequences , *MATHEMATICS - Abstract
In this paper we investigate colorings of sets avoiding similarly colored subsets. If
S is an arbitrary colored set andT is a fixed family of bijections ofS to itself, then two subsetsA,B⊆S are said to be colored similarly with respect toT , if there exists a transformationt∈T mappingA ontoB , and preserving a coloring ofA . This general setting covers some well-known topics such as non-repetitive sequences of Thue or the famous Hadwiger–Nelson problem on unit distances in Euclidean spaces. Our main theorem of this paper concerns arbitrary infinite sets, however, the most striking consequences are obtained for the case of Euclidean spaces. For instance, there exist 2-colorings ofRn with no two different line segments colored similarly, with respect to translations. The method is based on the principle of induction, hence it is not constructive in general, and the problem of explicit constructions arises naturally. We give two such examples of non-repetitive colorings of the setsR andQ , with respect to translations. In conclusion of the paper we discuss possible generalizations and pose two open problems. [Copyright &y& Elsevier]- Published
- 2003
- Full Text
- View/download PDF
20. Notes on the shadow process in self–dual codes
- Author
-
Ozeki, Michio
- Subjects
- *
BINARY number system , *MATHEMATICS - Abstract
In the present paper we present some tools in exploring the shadow process in self–dual codes for the purpose of finding singly even self–dual binary codes with higher minimal distances. The present paper can be viewed as a supplementary work to the preceding works (IEEE Trans. Inform. Theory 36 (1990) 1319; IEEE Trans. Inform Theory 37 (1991) 1222). [Copyright &y& Elsevier]
- Published
- 2003
- Full Text
- View/download PDF
21. An infinite family of subcubic graphs with unbounded packing chromatic number.
- Author
-
Brešar, Boštjan and Ferme, Jasmina
- Subjects
- *
GROUP theory , *ABSTRACT algebra , *INFINITY (Mathematics) , *MATHEMATICS , *MATHEMATICAL bounds - Abstract
Recently, Balogh et al. (2018) answered in negative the question that was posed in several earlier papers whether the packing chromatic number is bounded in the class of graphs with maximum degree 3. In this note, we present an explicit infinite family of subcubic graphs with unbounded packing chromatic number. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
22. Group-labeled light dual multinets in the projective plane.
- Author
-
Korchmáros, Gábor and Nagy, Gábor P.
- Subjects
- *
GROUP theory , *FINITE groups , *ABSTRACT algebra , *SET theory , *MATHEMATICS - Abstract
In this paper we investigate light dual multinets labeled by a finite group in the projective plane P G ( 2 , K ) defined over a field K . We present two classes of new examples. Moreover, under some conditions on the characteristic of K , we classify group-labeled light dual multinets with lines of length at least 9. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
23. Flag-transitive block designs with automorphism group [formula omitted].
- Author
-
Braić, Snježana, Mandić, Joško, and Vučičić, Tanja
- Subjects
- *
AUTOMORPHISMS , *GROUP theory , *BLOCK designs , *MULTIPLY transitive groups , *MATHEMATICS - Abstract
In this paper we consider the possibility that groups S n w r S 2 , 4 ≤ n ≤ 63 , act flag-transitively on block designs with n 2 points. We rule out n ∈ { 7 , 11 , 15 , 19 , 23 , 31 , 35 , 43 , 47 , 59 } and confirm the required action for other n in the given range through performing the construction of base blocks of the desired designs. Our construction makes use of flag-transitive incidence structures and weakly flag-transitive incidence structures. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
24. Sufficient conditions for the existence of pseudo 2-factors without isolated vertices and small odd cycles.
- Author
-
Egawa, Yoshimi and Furuya, Michitaka
- Subjects
- *
GEOMETRIC vertices , *GRAPH theory , *ISOMORPHISM (Mathematics) , *MATHEMATICS , *CATEGORIES (Mathematics) - Abstract
A spanning subgraph F of a graph G is called a { P 2 , C 2 i + 1 : i ≥ k } -factor if each component of F is isomorphic to either a path of order 2 or a cycle of order 2 i + 1 for some i ≥ k . In this paper, we obtain the following two results (here c i ( G − X ) is the number of components C of G − X with | V ( C ) | = i ): (i) If a graph G satisfies c 1 ( G − X ) + c 3 ( G − X ) ≤ 1 2 | X | for all X ⊆ V ( G ) , then G has a { P 2 , C 2 i + 1 : i ≥ 2 } -factor. (ii) For k ≥ 3 , if a graph G satisfies ∑ 0 ≤ j ≤ k − 1 c 2 j + 1 ( G − X ) ≤ 2 5 ( k 2 − 1 ) | X | for all X ⊆ V ( G ) , then G has a { P 2 , C 2 i + 1 : i ≥ k } -factor. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
25. Blocker size via matching minors.
- Author
-
Yolov, Nikola
- Subjects
- *
GEOMETRIC vertices , *GRAPH theory , *INDEPENDENT sets , *MATHEMATICS , *ANGLES - Abstract
Finding the maximum number of maximal independent sets in an n -vertex graph G , i ( G ) , from a restricted class is an extensively studied problem. Let k K 2 denote the matching of size k , that is a graph with 2 k vertices and k disjoint edges. A graph with an induced copy of k K 2 contains at least 2 k maximal independent sets. The other direction was established in a series of papers (Farber, 1989; Balas and Yu, 1989; Farber, 1993) finally yielding i ( G ) ≤ ( n ∕ k ) 2 k for a graph G without an induced ( k + 1 ) K 2 . Alekseev proved in Alekseev (2007) that i ( G ) is at most the number of induced matchings of G . This work generalises the aforementioned results to clutters. The right substructures in this setting are minors rather than induced subgraphs. Maximal independent sets of a clutter H are in one-to-one correspondence to the sets of its blocker, b ( H ) , hence i ( H ) = | b ( H ) | . We show that | b ( H ) | ≤ ∑ m = 0 k ⋅ f ( r ) | H | m r 2 m for a ( k + 1 ) K 2 -minor-free clutter H where f ( r ) = ( 2 r − 3 ) 2 r − 2 and r is the maximum size of a set in H . A key step in the proofs is, similarly to Alekseev’s result, showing that i ( H ) is bounded by the number of a substructure called semi-matching, and then proving a dependence between the number of semi-matchings and the number of minor matchings. Note that similarly to graphs, a clutter containing a k K 2 minor has at least 2 k maximal independent sets. From a computational perspective, a polynomial number of independent sets is particularly interesting. Our results lead to polynomial algorithms for restricted instances of many problems including Set Cover and k -SAT. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
26. Decomposing 8-regular graphs into paths of length 4.
- Author
-
Botler, F. and Talon, A.
- Subjects
- *
MATHEMATICAL decomposition , *REGULAR graphs , *PATHS & cycles in graph theory , *MATHEMATICAL proofs , *MATHEMATICS - Abstract
A T -decomposition of a graph G is a set of edge-disjoint copies of T in G that cover the edge set of G . Graham and Häggkvist (1989) conjectured that any 2 ℓ -regular graph G admits a T -decomposition if T is a tree with ℓ edges. Kouider and Lonc (1999) conjectured that, in the special case where T is the path with ℓ edges, G admits a T -decomposition D where every vertex of G is the end-vertex of exactly two paths of D , and proved that this statement holds when G has girth at least ( ℓ + 3 ) ∕ 2 . In this paper we verify Kouider and Lonc’s Conjecture for paths of length 4 . [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
27. Circumferences of 3-connected claw-free graphs, II.
- Author
-
Chen, Zhi-Hong
- Subjects
- *
GRAPH theory , *MATHEMATICAL proofs , *PROBLEM solving , *PETERSEN graphs , *MATHEMATICS - Abstract
For a graph H , the circumference of H , denoted by c ( H ) , is the length of a longest cycle in H . It is proved in Chen (2016) that if H is a 3-connected claw-free graph of order n with δ ≥ 8 , then c ( H ) ≥ min { 9 δ − 3 , n } . In Li (2006), Li conjectured that every 3-connected k -regular claw-free graph H of order n has c ( H ) ≥ min { 10 k − 4 , n } . Later, Li posed an open problem in Li (2008): how long is the best possible circumference for a 3-connected regular claw-free graph? In this paper, we study the circumference of 3-connected claw-free graphs without the restriction on regularity and provide a solution to the conjecture and the open problem above. We determine five families F i ( 1 ≤ i ≤ 5 ) of 3-connected claw-free graphs which are characterized by graphs contractible to the Petersen graph and show that if H is a 3-connected claw-free graph of order n with δ ≥ 16 , then one of the following holds: (a) either c ( H ) ≥ min { 10 δ − 3 , n } or H ∈ F 1 . (b) either c ( H ) ≥ min { 11 δ − 7 , n } or H ∈ F 1 ∪ F 2 . (c) either c ( H ) ≥ min { 11 δ − 3 , n } or H ∈ F 1 ∪ F 2 ∪ F 3 . (d) either c ( H ) ≥ min { 12 δ − 10 , n } or H ∈ F 1 ∪ F 2 ∪ F 3 ∪ F 4 . (e) if δ ≥ 23 then either c ( H ) ≥ min { 12 δ − 7 , n } or H ∈ F 1 ∪ F 2 ∪ F 3 ∪ F 4 ∪ F 5 . This is also an improvement of the prior results in Chen (2016), Lai et al. (2016), Li et al. (2009) and Mathews and Sumner (1985). [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
28. Spanning trees with leaf distance at least [formula omitted].
- Author
-
Erbes, C., Molla, T., Mousley, S., and Santana, M.
- Subjects
- *
SPANNING trees , *TREE graphs , *LOGICAL prediction , *INTEGERS , *MATHEMATICS - Abstract
The leaf distance of a tree is the maximum d such that the distance between any pair of leaves in the tree is at least d . Kaneko provided sufficient conditions to force the existence of a spanning tree with leaf distance at least d = 3 and conjectured that similar conditions suffice for larger d . The case when d = 4 was later proved by Kaneko, Kano, and Suzuki. In this paper, we show that when d ≥ 4 , a stronger form of this conjecture holds for graphs with independence number at most five. As an immediate corollary, we obtain that when d ≥ n ∕ 3 , this stronger version holds for all n -vertex graphs, consequently proving Kaneko’s conjecture for d ≥ n ∕ 3 . [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
29. A note on embedding graphs without short cycles
- Author
-
Görlich, Agnieszka, Pilśniak, Monika, Woźniak, Mariusz, and Ziolo, Irmina A.
- Subjects
- *
EMBEDDING theorems , *EMBEDDINGS (Mathematics) , *ALGEBRAIC geometry , *MATHEMATICS - Abstract
Let
k⩾3 be an integer. Denote byTk the following statement:If a graphG is a non-star graph without cycles of length⩽k thenG is a subgraph of its complement.It has been conjectured by Faudree, Rousseau, Schelp and Schuster thatT4 holds. As far as we know the best general result is in the paper of Brandt who proved thatT6 holds.In this paper we give an another, relatively short proof of Brandt''s result. [Copyright &y& Elsevier]- Published
- 2004
- Full Text
- View/download PDF
30. Two-dimensional balanced sampling plans avoiding adjacent units.
- Author
-
Wang, Xiaomiao, Feng, Tao, Zhang, Jing, and Xu, Yan
- Subjects
- *
DIMENSION theory (Topology) , *STATISTICAL sampling , *POLYGONS , *MATHEMATICS , *MATHEMATICAL analysis - Abstract
Hedayat et al. first introduced balanced sampling plans for the exclusion of contiguous units. Wright detailed the results of a preliminary investigation of two-dimensional balanced sampling plans avoiding adjacent units (2-BSAs), and pointed out explicitly three types of 2-BSAs, which have different adjacency scheme, namely “Row and Column”, “Sharing a Border” and “Island”. This paper will provide more details for the three types of 2-BSAs from the point of view of design theory. [ABSTRACT FROM AUTHOR]
- Published
- 2015
- Full Text
- View/download PDF
31. More on the Terwilliger algebra of Johnson schemes.
- Author
-
Lv, Benjian, Maldonado, Carolina, and Wang, Kaishun
- Subjects
- *
ALGEBRA , *GRAPH theory , *PATHS & cycles in graph theory , *MATHEMATICS , *MATHEMATICAL analysis - Abstract
Abstract: In Levstein and Maldonado (2007), the Terwilliger algebra of the Johnson scheme was determined when . In this paper, we determine the Terwilliger algebra for the remaining case . [Copyright &y& Elsevier]
- Published
- 2014
- Full Text
- View/download PDF
32. New large sets of resolvable Mendelsohn triple systems.
- Author
-
Zhou, Junling and Chang, Yanxun
- Subjects
- *
SET theory , *GENERALIZATION , *EXISTENCE theorems , *PAIRED comparisons (Mathematics) , *MATHEMATICS , *MATHEMATICAL analysis - Abstract
Abstract: An LRMTS is a large set consisting of pairwise disjoint resolvable Mendelsohn triple systems defined over the same -element set. In this paper a new product construction for LRMTS is displayed by using generalized LR-designs. As well, several new existence families of LRMTS are constructed via 3-wise balanced designs. Finally the existence result of LRMTS is expanded by combining all the known constructions. [Copyright &y& Elsevier]
- Published
- 2014
- Full Text
- View/download PDF
33. The flower intersection problem for ’s.
- Author
-
Zhang, Guizhi, Chang, Yanxun, and Feng, Tao
- Subjects
- *
INTERSECTION theory , *PROBLEM solving , *STEINER systems , *INTEGERS , *MATHEMATICS , *MATHEMATICAL analysis - Abstract
Abstract: A flower in a Steiner system is the set of all blocks containing a given point. The flower intersection problem for Steiner systems is the determination of all pairs such that there exists a pair of Steiner systems and of order having a common flower satisfying . In this paper the flower intersection problem for a pair of ’s is investigated. Let a pair of ’s intersecting in blocks, of them being the blocks of a common flower . Let , where and is the number of blocks of an . It is established that for any positive integer and . [Copyright &y& Elsevier]
- Published
- 2014
- Full Text
- View/download PDF
34. Summation formulae for -Watson type -series.
- Author
-
Wei, Chuanan, Gong, Dianxuan, and Li, Jianbo
- Subjects
- *
MATHEMATICAL formulas , *MATHEMATICAL analysis , *MATHEMATICAL series , *MATHEMATICS , *INFINITE processes , *MATHEMATICAL sequences - Abstract
Abstract: We use the method of series rearrangement to establish two families of summation formulae for -Watson type -series in this paper. [Copyright &y& Elsevier]
- Published
- 2013
- Full Text
- View/download PDF
35. Conics and multiple derivation
- Author
-
Barwick, S.G. and Marshall, D.J.
- Subjects
- *
SET theory , *MULTIPLICITY (Mathematics) , *PLANE geometry , *MATHEMATICAL analysis , *MATHEMATICS , *CLUSTER set theory - Abstract
Abstract: Let be a conic in and suppose we derive with respect to a derivation set or multiple derivation set. This paper looks at whether the conic gives rise to an inherited arc in the derived plane. Further, we construct two families of conics which give rise to inherited arcs after certain double derivations. Finally we construct a family of complete -arcs in certain André planes. [Copyright &y& Elsevier]
- Published
- 2012
- Full Text
- View/download PDF
36. Neighborhood unions and disjoint chorded cycles in graphs
- Author
-
Qiao, Shengning
- Subjects
- *
GRAPH theory , *HAMILTONIAN graph theory , *RINGS of integers , *VERTEX operator algebras , *MATHEMATICS , *MATHEMATICAL analysis - Abstract
Abstract: Let be two integers and be a graph with at least vertices. In this paper, we show that if for any two nonadjacent vertices and in , then contains vertex-disjoint cycles such that of them are chorded cycles. The condition is sharp. [Copyright &y& Elsevier]
- Published
- 2012
- Full Text
- View/download PDF
37. On the minimal eccentric connectivity indices of graphs
- Author
-
Zhang, Jianbin, Zhou, Bo, and Liu, Zhongzhu
- Subjects
- *
GRAPH theory , *GRAPH connectivity , *DIAMETER , *MAXIMA & minima , *MATHEMATICS , *NUMERICAL analysis - Abstract
Abstract: Let be a simple connected graph. The eccentric connectivity index of is defined as , where the eccentricity is the largest distance between and any other vertex of . In this paper, we obtain lower bounds on in terms of the number of edges among -vertex connected graphs with given diameter. Over connected graphs on vertices with edges and diameter at least , and connected graphs on vertices with diameter at least , we provide lower bounds on and characterize the extremal graphs, respectively. [Copyright &y& Elsevier]
- Published
- 2012
- Full Text
- View/download PDF
38. The fine triangle intersection problem for kite systems
- Author
-
Chang, Yanxun, Feng, Tao, Lo Faro, Giovanni, and Tripodi, Antoinette
- Subjects
- *
TRIANGLES , *INTERSECTION theory , *RINGS of integers , *EXTREMAL problems (Mathematics) , *MATHEMATICS , *MATHEMATICAL analysis - Abstract
Abstract: In this paper, we introduce the concept of the fine triangle intersection problem for a pair of -designs, and we consider this problem for kite systems. Let . Let , where . We establish that, for any positive integer and , . [Copyright &y& Elsevier]
- Published
- 2012
- Full Text
- View/download PDF
39. Cycles in -traceable oriented graphs
- Author
-
van Aardt, Susan A., Dunbar, Jean E., Frick, Marietjie, and Nielsen, Morten H.
- Subjects
- *
PATHS & cycles in graph theory , *DIRECTED graphs , *PARTITIONS (Mathematics) , *LINE geometry , *GAME theory , *SET theory , *MATHEMATICS , *MATHEMATICAL analysis - Abstract
Abstract: A digraph of order at least is termed -traceable if each of its subdigraphs of order is traceable. It turns out that several properties of tournaments—i.e., the 2-traceable oriented graphs—extend to -traceable oriented graphs for small values of . For instance, the authors together with O. Oellermann have recently shown that for , all -traceable oriented graphs are traceable. Moon [J.W. Moon, On subtournaments of a tournament, Canad. Math. Bull. 9(3) (1966) 297–301] observed that every nontrivial strong tournament is vertex-pancyclic—i.e., through each vertex there is a cycle of every length from 3 up to the order of . The present paper reports results pertaining to various cycle properties of strong -traceable oriented graphs and explores the extent to which pancyclicity is retained by strong -traceable oriented graphs. For each there are infinitely many -traceable oriented graphs—e.g. tournaments. However, we establish an upper bound (linear in ) on the order of -traceable oriented graphs having a strong component with girth greater than 3. As an application of our findings, we show that the Path Partition Conjecture holds for 1-deficient oriented graphs having a strong component with girth at least 6. (A digraph is 1-deficient if its order is exactly one more than the order of its longest paths.) [Copyright &y& Elsevier]
- Published
- 2011
- Full Text
- View/download PDF
40. Acyclic 5-choosability of planar graphs with neither 4-cycles nor chordal 6-cycles
- Author
-
Zhang, Haihui and Xu, Baogang
- Subjects
- *
GRAPH theory , *MATHEMATICAL analysis , *COMBINATORICS , *PATHS & cycles in graph theory , *MATHEMATICS - Abstract
Abstract: A proper vertex coloring of a graph is acyclic if contains no bicolored cycle. A graph is acyclically -list colorable if for a given list assignment , there exists a proper acyclic coloring of such that for all . If is acyclically -list colorable for any list assignment with for all , then is acyclically -choosable. In this paper it is proved that every planar graph with neither 4-cycles nor chordal 6-cycles is acyclically 5-choosable. This generalizes the results of [M. Montassier, A. Raspaud, W. Wang, Acyclic 5-choosability of planar graphs without small cycles, J. Graph Theory 54 (2007) 245–260], and a corollary of [M. Montassier, P. Ochem, A. Raspaud, On the acyclic choosability of graphs, J. Graph Theory 51 (4) (2006) 281–300]. [Copyright &y& Elsevier]
- Published
- 2009
- Full Text
- View/download PDF
41. A -analogue of Zhang’s binomial coefficient identities
- Author
-
Guo, Victor J.W., Lin, Ying-Jie, Liu, Yan, and Zhang, Cai
- Subjects
- *
BINOMIAL coefficients , *COMBINATORIAL identities , *MATHEMATICAL analysis , *COMBINATORICS , *MATHEMATICAL combinations , *MATHEMATICS - Abstract
Abstract: In this paper, we prove some identities for the alternating sums of squares and cubes of the partial sum of the -binomial coefficients. Our proof also leads to a -analogue of the sum of the first squares due to Schlosser. [Copyright &y& Elsevier]
- Published
- 2009
- Full Text
- View/download PDF
42. Edge-deletable IM-extendable graphs with minimum number of edges
- Author
-
Wang, Xiumei, Yuan, Jinjiang, and Zhou, Sujing
- Subjects
- *
GRAPH theory , *MATHEMATICAL analysis , *COMBINATORICS , *ALGEBRA , *MATHEMATICS - Abstract
Abstract: A graph is induced matching extendable, shortly IM-extendable, if every induced matching of is included in a perfect matching of . For a nonnegative integer , a graph is called a -edge-deletable IM-extendable graph, if, for every with , is IM-extendable. In this paper, we characterize the -edge-deletable IM-extendable graphs with minimum number of edges. We show that, for a positive integer , if is a-edge-deletable IM-extendable graph on vertices, then ; furthermore, the equality holds if and only if either , or for some integer and , where is the empty graph on vertices and is the graph obtained from by replacing each vertex with a graph isomorphic to . [Copyright &y& Elsevier]
- Published
- 2009
- Full Text
- View/download PDF
43. On the -domination number of Cartesian products of graphs
- Author
-
Hou, Xinmin and Lu, You
- Subjects
- *
DOMINATING set , *GRAPHIC methods , *COMBINATORIAL packing & covering , *MATHEMATICAL proofs , *PRODUCTS of subgroups , *MATHEMATICS - Abstract
Abstract: Let denote the Cartesian product of graphs and . In this paper, we study the -domination number of Cartesian product of graphs and give a new lower bound of in terms of packing and -domination numbers of and . As applications of this lower bound, we prove that: (i) For , the new lower bound improves the bound given by Chen, et al. [G. Chen, W. Piotrowski, W. Shreve, A partition approach to Vizing’s conjecture, J. Graph Theory 21 (1996) 103–111]. (ii) The product of the -domination numbers of two any graphs and , at least one of which is a -graph, is no more than . (iii) The product of the -domination numbers of any graphs and , at least one of which is a -graph, is no more than . [Copyright &y& Elsevier]
- Published
- 2009
- Full Text
- View/download PDF
44. Complete solution for the rainbow numbers of matchings
- Author
-
Chen, He, Li, Xueliang, and Tu, Jianhua
- Subjects
- *
GRAPH coloring , *RINGS of integers , *GRAPH theory , *MATCHING theory , *MATHEMATICS - Abstract
Abstract: For a given graph and a positive , the rainbow number of , denoted by , is the minimum integer so that in any edge-coloring of with colors there is a copy of whose edges have distinct colors. In 2004, Schiermeyer determined for all . The case for smaller values of (namely, ) remained generally open. In this paper we extend Schiermeyer’s result to all plausible and hence determine the rainbow number of matchings. [Copyright &y& Elsevier]
- Published
- 2009
- Full Text
- View/download PDF
45. Common circulant homogeneous factorisations of the complete digraph
- Author
-
Praeger, Cheryl, Li, Cai Heng, and Stringer, Linda
- Subjects
- *
FACTORIZATION , *COMPLETE graphs , *RINGS of integers , *PERMUTATION groups , *ALGEBRAIC cycles , *MATHEMATICS - Abstract
Abstract: In this paper we determine the positive integers and for which there exists a homogeneous factorisation of a complete digraph on vertices with ‘common circulant’ factors. This means a partition of the arc set of the complete digraph into circulant factor digraphs, such that a cyclic group of order acts regularly on the vertices of each factor digraph whilst preserving the edges, and in addition, an overgroup of this permutes the factor digraphs transitively amongst themselves. This determination generalises a previous result for self-complementary circulants. [Copyright &y& Elsevier]
- Published
- 2009
- Full Text
- View/download PDF
46. Vertex pancyclicity in quasi-claw-free graphs
- Author
-
Qu, Ellen X.Y. and Wang, Jianglu
- Subjects
- *
GRAPH connectivity , *GRAPH theory , *MATHEMATICAL analysis , *COMBINATORICS , *ALGEBRA , *MATHEMATICS - Abstract
Abstract: A graph is called quasi-claw-free if for any two vertices and with distance two there exists a vertex such that . This concept is a natural extension of the classical claw-free graphs. In this paper, we present two sufficient conditions for vertex pancyclicity in quasi-claw-free graphs, namely, quasilocally connected and almost locally connected graphs. Our results include some well-known results on claw-free graphs as special cases. We also give an affirmative answer to a problem proposed by Ainouche. [Copyright &y& Elsevier]
- Published
- 2009
- Full Text
- View/download PDF
47. On canonical antichains
- Author
-
Ding, Guoli
- Subjects
- *
PARTIALLY ordered sets , *GRAPH theory , *MATHEMATICAL analysis , *MATHEMATICS , *COMBINATORICS , *ALGEBRA - Abstract
Abstract: An antichain of a well-founded quasi-order is canonical if for every ideal of , has an infinite antichain if and only if is infinite. In this paper we characterize the obstructions to having a canonical antichain. As an application we show that, under the induced subgraph relation, the class of finite graphs does not have a canonical antichain. In contrast, this class does have a canonical antichain with respect to the subgraph relation. [Copyright &y& Elsevier]
- Published
- 2009
- Full Text
- View/download PDF
48. The edge version of Hadwiger’s conjecture
- Author
-
Ding, Guoli
- Subjects
- *
GRAPH connectivity , *MATHEMATICAL analysis , *GRAPH theory , *MATHEMATICS , *COMBINATORICS , *ALGEBRA - Abstract
Abstract: A well known conjecture of Hadwiger asserts that is the only minor minimal graph of chromatic number greater than . In this paper, all minor minimal graphs of chromatic index greater than are determined. [Copyright &y& Elsevier]
- Published
- 2009
- Full Text
- View/download PDF
49. Codiameters of 3-domination critical graphs with toughness more than one
- Author
-
Edwin Cheng, T.C., Chen, Yaojun, and Ng, C.T.
- Subjects
- *
DOMINATING set , *HAMILTONIAN graph theory , *GRAPH connectivity , *GRAPH theory , *MATHEMATICAL analysis , *MATHEMATICS - Abstract
Abstract: A graph is 3-domination-critical (3-critical, for short), if its domination number is 3 and the addition of any edge decreases by 1. In this paper, we show that every 3-critical graph with independence number 4 and minimum degree 3 is Hamilton-connected. Combining the result with those in [Y.J. Chen, F. Tian, B. Wei, Hamilton-connectivity of 3-domination critical graphs with , Discrete Mathematics 271 (2003) 1–12; Y.J. Chen, F. Tian, Y.Q. Zhang, Hamilton-connectivity of 3-domination critical graphs with , European Journal of Combinatorics 23 (2002) 777–784; Y.J. Chen, T.C.E. Cheng, C.T. Ng, Hamilton-connectivity of 3-domination critical graphs with , Discrete Mathematics 308 (2008) (in press)], we solve the following conjecture: a connected 3-critical graph is Hamilton-connected if and only if , where is the toughness of . [Copyright &y& Elsevier]
- Published
- 2009
- Full Text
- View/download PDF
50. Long cycles in 4-connected planar graphs
- Author
-
Cui, Qing, Hu, Yumei, and Wang, Jian
- Subjects
- *
ALGEBRAIC cycles , *GRAPH connectivity , *HAMILTONIAN graph theory , *GRAPH theory , *MATHEMATICAL analysis , *MATHEMATICS - Abstract
Abstract: Let be a 4-connected planar graph on vertices. Malkevitch conjectured that if contains a cycle of length 4, then contains a cycle of length for every . This conjecture is true for every with . In this paper, we prove that also has a cycle of length provided . [Copyright &y& Elsevier]
- Published
- 2009
- Full Text
- View/download PDF
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.