Displaying similar documents to “Embedding products of graphs into Euclidean spaces”

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...

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 .

Note on improper coloring of 1 -planar graphs

Yanan Chu, Lei Sun, Jun Yue (2019)

Czechoslovak Mathematical Journal

Similarity:

A graph G = ( V , E ) is called improperly ( d 1 , , d k ) -colorable if the vertex set V can be partitioned into subsets V 1 , , V k such that the graph G [ V i ] induced by the vertices of V i has maximum degree at most d i for all 1 i k . In this paper, we mainly study the improper coloring of 1 -planar graphs and show that 1 -planar graphs with girth at least 7 are ( 2 , 0 , 0 , 0 ) -colorable.

Note on a conjecture for the sum of signless Laplacian eigenvalues

Xiaodan Chen, Guoliang Hao, Dequan Jin, Jingjian Li (2018)

Czechoslovak Mathematical Journal

Similarity:

For a simple graph G on n vertices and an integer k with 1 k n , denote by 𝒮 k + ( G ) the sum of k largest signless Laplacian eigenvalues of G . It was conjectured that 𝒮 k + ( G ) e ( G ) + k + 1 2 , where e ( G ) is the number of edges of G . This conjecture has been proved to be true for all graphs when k { 1 , 2 , n - 1 , n } , and for trees, unicyclic graphs, bicyclic graphs and regular graphs (for all k ). In this note, this conjecture is proved to be true for all graphs when k = n - 2 , and for some new classes of graphs.

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...

Resolving sets of directed Cayley graphs for the direct product of cyclic groups

Demelash Ashagrie Mengesha, Tomáš Vetrík (2019)

Czechoslovak Mathematical Journal

Similarity:

A directed Cayley graph C ( Γ , X ) is specified by a group Γ and an identity-free generating set X for this group. Vertices of C ( Γ , X ) are elements of Γ and there is a directed edge from the vertex u to the vertex v in C ( Γ , X ) if and only if there is a generator x X such that u x = v . We study graphs C ( Γ , X ) for the direct product Z m × Z n of two cyclic groups Z m and Z n , and the generating set X = { ( 0 , 1 ) , ( 1 , 0 ) , ( 2 , 0 ) , , ( p , 0 ) } . We present resolving sets which yield upper bounds on the metric dimension of these graphs for p = 2 and 3 .

Saturation numbers for linear forests P 6 + t P 2

Jingru Yan (2023)

Czechoslovak Mathematical Journal

Similarity:

A graph G is H -saturated if it contains no H as a subgraph, but does contain H after the addition of any edge in the complement of G . The saturation number, sat ( n , H ) , is the minimum number of edges of a graph in the set of all H -saturated graphs of order n . We determine the saturation number sat ( n , P 6 + t P 2 ) for n 10 3 t + 10 and characterize the extremal graphs for n > 10 3 t + 20 .

Generalized 3-edge-connectivity of Cartesian product graphs

Yuefang Sun (2015)

Czechoslovak Mathematical Journal

Similarity:

The generalized k -connectivity κ k ( G ) of a graph G was introduced by Chartrand et al. in 1984. As a natural counterpart of this concept, Li et al. in 2011 introduced the concept of generalized k -edge-connectivity which is defined as λ k ( G ) = min { λ ( S ) : S V ( G ) and | S | = k } , where λ ( S ) denotes the maximum number of pairwise edge-disjoint trees T 1 , T 2 , ... , T in G such that S V ( T i ) for 1 i . In this paper we prove that for any two connected graphs G and H we have λ 3 ( G H ) λ 3 ( G ) + λ 3 ( H ) , where G H is the Cartesian product of G and H . Moreover, the bound is sharp. We also...

Maximum bipartite subgraphs in H -free graphs

Jing Lin (2022)

Czechoslovak Mathematical Journal

Similarity:

Given a graph G , let f ( G ) denote the maximum number of edges in a bipartite subgraph of G . Given a fixed graph H and a positive integer m , let f ( m , H ) denote the minimum possible cardinality of f ( G ) , as G ranges over all graphs on m edges that contain no copy of H . In this paper we prove that f ( m , θ k , s ) 1 2 m + Ω ( m ( 2 k + 1 ) / ( 2 k + 2 ) ) , which extends the results of N. Alon, M. Krivelevich, B. Sudakov. Write K k ' and K t , s ' for the subdivisions of K k and K t , s . We show that f ( m , K k ' ) 1 2 m + Ω ( m ( 5 k - 8 ) / ( 6 k - 10 ) ) and f ( m , K t , s ' ) 1 2 m + Ω ( m ( 5 t - 1 ) / ( 6 t - 2 ) ) , improving a result of Q. Zeng, J. Hou. We also give lower bounds on...

The real symmetric matrices of odd order with a P-set of maximum size

Zhibin Du, Carlos Martins da Fonseca (2016)

Czechoslovak Mathematical Journal

Similarity:

Suppose that A is a real symmetric matrix of order n . Denote by m A ( 0 ) the nullity of A . For a nonempty subset α of { 1 , 2 , ... , n } , let A ( α ) be the principal submatrix of A obtained from A by deleting the rows and columns indexed by α . When m A ( α ) ( 0 ) = m A ( 0 ) + | α | , we call α a P-set of A . It is known that every P-set of A contains at most n / 2 elements. The graphs of even order for which one can find a matrix attaining this bound are now completely characterized. However, the odd case turned out to be more difficult to tackle. As...

A note on the double Roman domination number of graphs

Xue-Gang Chen (2020)

Czechoslovak Mathematical Journal

Similarity:

For a graph G = ( V , E ) , a double Roman dominating function is a function f : V { 0 , 1 , 2 , 3 } having the property that if f ( v ) = 0 , then the vertex v must have at least two neighbors assigned 2 under f or one neighbor with f ( w ) = 3 , and if f ( v ) = 1 , then the vertex v must have at least one neighbor with f ( w ) 2 . The weight of a double Roman dominating function f is the sum f ( V ) = v V f ( v ) . The minimum weight of a double Roman dominating function on G is called the double Roman domination number of G and is denoted by γ dR ( G ) . In this paper, we establish a new...