Displaying similar documents to “Equivalent classes for K₃-gluings of wheels”

On characterization of uniquely 3-list colorable complete multipartite graphs

Yancai Zhao, Erfang Shan (2010)

Discussiones Mathematicae Graph Theory

Similarity:

For each vertex v of a graph G, if there exists a list of k colors, L(v), such that there is a unique proper coloring for G from this collection of lists, then G is called a uniquely k-list colorable graph. Ghebleh and Mahmoodian characterized uniquely 3-list colorable complete multipartite graphs except for nine graphs: K 2 , 2 , r r ∈ 4,5,6,7,8, K 2 , 3 , 4 , K 1 * 4 , 4 , K 1 * 4 , 5 , K 1 * 5 , 4 . Also, they conjectured that the nine graphs are not U3LC graphs. After that, except for K 2 , 2 , r r ∈ 4,5,6,7,8, the others have been proved not...

Intrinsic linking and knotting are arbitrarily complex

Erica Flapan, Blake Mellor, Ramin Naimi (2008)

Fundamenta Mathematicae

Similarity:

We show that, given any n and α, any embedding of any sufficiently large complete graph in ℝ³ contains an oriented link with components Q₁, ..., Qₙ such that for every i ≠ j, | l k ( Q i , Q j ) | α and | a ( Q i ) | α , where a ( Q i ) denotes the second coefficient of the Conway polynomial of Q i .

Generalized list colourings of graphs

Mieczysław Borowiecki, Ewa Drgas-Burchardt, Peter Mihók (1995)

Discussiones Mathematicae Graph Theory

Similarity:

We prove: (1) that c h P ( G ) - χ P ( G ) can be arbitrarily large, where c h P ( G ) and χ P ( G ) are P-choice and P-chromatic numbers, respectively, (2) the (P,L)-colouring version of Brooks’ and Gallai’s theorems.

Remarks on D -integral complete multipartite graphs

Pavel Híc, Milan Pokorný (2016)

Czechoslovak Mathematical Journal

Similarity:

A graph is called distance integral (or D -integral) if all eigenvalues of its distance matrix are integers. In their study of D -integral complete multipartite graphs, Yang and Wang (2015) posed two questions on the existence of such graphs. We resolve these questions and present some further results on D -integral complete multipartite graphs. We give the first known distance integral complete multipartite graphs K p 1 , p 2 , p 3 with p 1 < p 2 < p 3 , and K p 1 , p 2 , p 3 , p 4 with p 1 < p 2 < p 3 < p 4 , as well as the infinite classes of distance integral...

Persistency in the Traveling Salesman Problem on Halin graphs

Vladimír Lacko (2000)

Discussiones Mathematicae Graph Theory

Similarity:

For the Traveling Salesman Problem (TSP) on Halin graphs with three types of cost functions: sum, bottleneck and balanced and with arbitrary real edge costs we compute in polynomial time the persistency partition E A l l , E S o m e , E N o n e of the edge set E, where: E A l l = e ∈ E, e belongs to all optimum solutions, E N o n e = e ∈ E, e does not belong to any optimum solution and E S o m e = e ∈ E, e belongs to some but not to all optimum solutions.

On choosability of complete multipartite graphs K 4 , 3 * t , 2 * ( k - 2 t - 2 ) , 1 * ( t + 1 )

Guo-Ping Zheng, Yu-Fa Shen, Zuo-Li Chen, Jin-Feng Lv (2010)

Discussiones Mathematicae Graph Theory

Similarity:

A graph G is said to be chromatic-choosable if ch(G) = χ(G). Ohba has conjectured that every graph G with 2χ(G)+1 or fewer vertices is chromatic-choosable. It is clear that Ohba’s conjecture is true if and only if it is true for complete multipartite graphs. In this paper we show that Ohba’s conjecture is true for complete multipartite graphs K 4 , 3 * t , 2 * ( k - 2 t - 2 ) , 1 * ( t + 1 ) for all integers t ≥ 1 and k ≥ 2t+2, that is, c h ( K 4 , 3 * t , 2 * ( k - 2 t - 2 ) , 1 * ( t + 1 ) ) = k , which extends the results c h ( K 4 , 3 , 2 * ( k - 4 ) , 1 * 2 ) = k given by Shen et al. (Discrete Math. 308 (2008) 136-143), and c h ( K 4 , 3 * 2 , 2 * ( k - 6 ) , 1 * 3 ) = k ...

2-halvable complete 4-partite graphs

Dalibor Fronček (1998)

Discussiones Mathematicae Graph Theory

Similarity:

A complete 4-partite graph K m , m , m , m is called d-halvable if it can be decomposed into two isomorphic factors of diameter d. In the class of graphs K m , m , m , m with at most one odd part all d-halvable graphs are known. In the class of biregular graphs K m , m , m , m with four odd parts (i.e., the graphs K m , m , m , n and K m , m , n , n ) all d-halvable graphs are known as well, except for the graphs K m , m , n , n when d = 2 and n ≠ m. We prove that such graphs are 2-halvable iff n,m ≥ 3. We also determine a new class of non-halvable graphs K m , m , m , m with three...

On distinguishing and distinguishing chromatic numbers of hypercubes

Werner Klöckl (2008)

Discussiones Mathematicae Graph Theory

Similarity:

The distinguishing number D(G) of a graph G is the least integer d such that G has a labeling with d colors that is not preserved by any nontrivial automorphism. The restriction to proper labelings leads to the definition of the distinguishing chromatic number χ D ( G ) of G. Extending these concepts to infinite graphs we prove that D ( Q ) = 2 and χ D ( Q ) = 3 , where Q denotes the hypercube of countable dimension. We also show that χ D ( Q ) = 4 , thereby completing the investigation of finite hypercubes with respect to χ D . Our...

Embedding products of graphs into Euclidean spaces

Mikhail Skopenkov (2003)

Fundamenta Mathematicae

Similarity:

For any collection of graphs G , . . . , G N we find the minimal dimension d such that the product G × . . . × G N is embeddable into d (see Theorem 1 below). In particular, we prove that (K₅)ⁿ and ( K 3 , 3 ) are not embeddable into 2 n , where K₅ and K 3 , 3 are the Kuratowski graphs. This is a solution of a problem of Menger from 1929. The idea of the proof is a reduction to a problem from so-called Ramsey link theory: we show that any embedding L k O S 2 n - 1 , where O is a vertex of (K₅)ⁿ, has a pair of linked (n-1)-spheres.

Edit distance measure for graphs

Tomasz Dzido, Krzysztof Krzywdziński (2015)

Czechoslovak Mathematical Journal

Similarity:

In this paper, we investigate a measure of similarity of graphs similar to the Ramsey number. We present values and bounds for g ( n , l ) , the biggest number k guaranteeing that there exist l graphs on n vertices, each two having edit distance at least k . By edit distance of two graphs G , F we mean the number of edges needed to be added to or deleted from graph G to obtain graph F . This new extremal number g ( n , l ) is closely linked to the edit distance of graphs. Using probabilistic methods we show...

Nearly complete graphs decomposable into large induced matchings and their applications

Noga Alon, Ankur Moitra, Benjamin Sudakov (2013)

Journal of the European Mathematical Society

Similarity:

We describe two constructions of (very) dense graphs which are edge disjoint unions of large induced matchings. The first construction exhibits graphs on N vertices with ( N 2 ) - o ( N 2 ) edges, which can be decomposed into pairwise disjoint induced matchings, each of size N 1 - o ( 1 ) . The second construction provides a covering of all edges of the complete graph K N by two graphs, each being the edge disjoint union of at most N 2 - δ induced matchings, where δ > 0 , 076 . This disproves (in a strong form) a conjecture of Meshulam,...

Paired domination in prisms of graphs

Christina M. Mynhardt, Mark Schurch (2011)

Discussiones Mathematicae Graph Theory

Similarity:

The paired domination number γ p r ( G ) of a graph G is the smallest cardinality of a dominating set S of G such that ⟨S⟩ has a perfect matching. The generalized prisms πG of G are the graphs obtained by joining the vertices of two disjoint copies of G by |V(G)| independent edges. We provide characterizations of the following three classes of graphs: γ p r ( π G ) = 2 γ p r ( G ) for all πG; γ p r ( K G ) = 2 γ p r ( G ) ; γ p r ( K G ) = γ p r ( G ) .

On generalized shift graphs

Christian Avart, Tomasz Łuczak, Vojtěch Rödl (2014)

Fundamenta Mathematicae

Similarity:

In 1968 Erdős and Hajnal introduced shift graphs as graphs whose vertices are the k-element subsets of [n] = 1,...,n (or of an infinite cardinal κ ) and with two k-sets A = a , . . . , a k and B = b , . . . , b k joined if a < a = b < a = b < < a k = b k - 1 < b k . They determined the chromatic number of these graphs. In this paper we extend this definition and study the chromatic number of graphs defined similarly for other types of mutual position with respect to the underlying ordering. As a consequence of our result, we show the existence of a graph with...

A note on the independent domination number versus the domination number in bipartite graphs

Shaohui Wang, Bing Wei (2017)

Czechoslovak Mathematical Journal

Similarity:

Let γ ( G ) and i ( G ) be the domination number and the independent domination number of G , respectively. Rad and Volkmann posted a conjecture that i ( G ) / γ ( G ) Δ ( G ) / 2 for any graph G , where Δ ( G ) is its maximum degree (see N. J. Rad, L. Volkmann (2013)). In this work, we verify the conjecture for bipartite graphs. Several graph classes attaining the extremal bound and graphs containing odd cycles with the ratio larger than Δ ( G ) / 2 are provided as well.

Classes of hypergraphs with sum number one

Hanns-Martin Teichert (2000)

Discussiones Mathematicae Graph Theory

Similarity:

A hypergraph ℋ is a sum hypergraph iff there are a finite S ⊆ ℕ⁺ and d̲,d̅ ∈ ℕ⁺ with 1 < d̲ < d̅ such that ℋ is isomorphic to the hypergraph d ̲ , d ̅ ( S ) = ( V , ) where V = S and = e S : d ̲ < | e | < d ̅ v e v S . For an arbitrary hypergraph ℋ the sum number(ℋ ) is defined to be the minimum number of isolatedvertices w , . . . , w σ V such that w , . . . , w σ is a sum hypergraph. For graphs it is known that cycles Cₙ and wheels Wₙ have sum numbersgreater than one. Generalizing these graphs we prove for the hypergraphs ₙ and ₙ that under a certain condition...

Distance independence in graphs

J. Louis Sewell, Peter J. Slater (2011)

Discussiones Mathematicae Graph Theory

Similarity:

For a set D of positive integers, we define a vertex set S ⊆ V(G) to be D-independent if u, v ∈ S implies the distance d(u,v) ∉ D. The D-independence number β D ( G ) is the maximum cardinality of a D-independent set. In particular, the independence number β ( G ) = β 1 ( G ) . Along with general results we consider, in particular, the odd-independence number β O D D ( G ) where ODD = 1,3,5,....

Edge-colouring of graphs and hereditary graph properties

Samantha Dorfling, Tomáš Vetrík (2016)

Czechoslovak Mathematical Journal

Similarity:

Edge-colourings of graphs have been studied for decades. We study edge-colourings with respect to hereditary graph properties. For a graph G , a hereditary graph property 𝒫 and l 1 we define χ 𝒫 , l ' ( G ) to be the minimum number of colours needed to properly colour the edges of G , such that any subgraph of G induced by edges coloured by (at most) l colours is in 𝒫 . We present a necessary and sufficient condition for the existence of χ 𝒫 , l ' ( G ) . We focus on edge-colourings of graphs with respect to the hereditary...

On 𝓕-independence in graphs

Frank Göring, Jochen Harant, Dieter Rautenbach, Ingo Schiermeyer (2009)

Discussiones Mathematicae Graph Theory

Similarity:

Let be a set of graphs and for a graph G let α ( G ) and α * ( G ) denote the maximum order of an induced subgraph of G which does not contain a graph in as a subgraph and which does not contain a graph in as an induced subgraph, respectively. Lower bounds on α ( G ) and α * ( G ) are presented.

Expansion in S L d ( 𝒪 K / I ) , I square-free

Péter P. Varjú (2012)

Journal of the European Mathematical Society

Similarity:

Let S be a fixed symmetric finite subset of S L d ( 𝒪 K ) that generates a Zariski dense subgroup of S L d ( 𝒪 K ) when we consider it as an algebraic group over m a t h b b Q by restriction of scalars. We prove that the Cayley graphs of S L d ( 𝒪 K / I ) with respect to the projections of S is an expander family if I ranges over square-free ideals of 𝒪 K if d = 2 and K is an arbitrary numberfield, or if d = 3 and K = .

Complete pluripolar graphs in N

Nguyen Quang Dieu, Phung Van Manh (2014)

Annales Polonici Mathematici

Similarity:

Let F be the Cartesian product of N closed sets in ℂ. We prove that there exists a function g which is continuous on F and holomorphic on the interior of F such that Γ g ( F ) : = ( z , g ( z ) ) : z F is complete pluripolar in N + 1 . Using this result, we show that if D is an analytic polyhedron then there exists a bounded holomorphic function g such that Γ g ( D ) is complete pluripolar in N + 1 . These results are high-dimensional analogs of the previous ones due to Edlund [Complete pluripolar curves and graphs, Ann. Polon. Math....