Mariusz Woźniak (1999)
Discussiones Mathematicae Graph Theory
Similarity:
An embedding of a simple graph G into its complement G̅ is a permutation σ on V(G) such that if an edge xy belongs to E(G), then σ(x)σ(y) does not belong to E(G). In this note we consider some families of embeddable graphs such that the corresponding permutation is cyclic.
Mariusz Woźniak (1998)
Discussiones Mathematicae Graph Theory
Similarity:
Let G be a simple graph of order n and size e(G). It is well known that if e(G) ≤ n-2, then there is an embedding G into its complement [G̅]. In this note, we consider a problem concerning the uniqueness of such an embedding.
M.-A. Tahraoui, E. Duchêne, H. Kheddouci (2017)
Discussiones Mathematicae Graph Theory
Similarity:
Graph packing generally deals with unlabeled graphs. In [4], the authors have introduced a new variant of the graph packing problem, called the labeled packing of a graph. This problem has recently been studied on trees [M.A. Tahraoui, E. Duchêne and H. Kheddouci, Labeled 2-packings of trees, Discrete Math. 338 (2015) 816-824] and cycles [E. Duchˆene, H. Kheddouci, R.J. Nowakowski and M.A. Tahraoui, Labeled packing of graphs, Australas. J. Combin. 57 (2013) 109-126]. In this note, we...
Woźniak Mariusz
Similarity:
PrefaceThere are two basic reference texts on packing theory: the last chapter of Bollobás's book [6] (1978) and the 4th chapter of Yap's book [85] (1986). They still remain the main references to packing problems. However, many papers related to these problems have recently been published and the reason for writing this survey is to gather in a systematic form results scattered throughout the literature.I wish I could name all who deserve my thanks. I am particularly grateful to A....
Justyna Otfinowska, Mariusz Woźniak (2013)
Discussiones Mathematicae Graph Theory
Similarity:
Let F be a forest of order n. It is well known that if F 6= Sn, a star of order n, then there exists an embedding of F into its complement F. In this note we consider a problem concerning the uniqueness of such an embedding.
Beata Orchel (1996)
Discussiones Mathematicae Graph Theory
Similarity:
In this paper we give all pairs of non mutually placeable (p,q)-bipartite graphs G and H such that 2 ≤ p ≤ q, e(H) ≤ p and e(G)+e(H) ≤ 2p+q-1.
Alewyn P. Burger, Christina M. Mynhardt, William D. Weakley (2004)
Discussiones Mathematicae Graph Theory
Similarity:
For a permutation π of the vertex set of a graph G, the graph π G is obtained from two disjoint copies G₁ and G₂ of G by joining each v in G₁ to π(v) in G₂. Hence if π = 1, then πG = K₂×G, the prism of G. Clearly, γ(G) ≤ γ(πG) ≤ 2 γ(G). We study graphs for which γ(K₂×G) = 2γ(G), those for which γ(πG) = 2γ(G) for at least one permutation π of V(G) and those for which γ(πG) = 2γ(G) for each permutation π of V(G).
D. de-Werra (1989)
Banach Center Publications
Similarity:
M. Woźniak (1995)
Discussiones Mathematicae Graph Theory
Similarity:
Let G be a simple graph of order n and size e(G). It is well known that if e(G) ≤ n-2, then there is an edge-disjoint placement of two copies of G into Kₙ. We prove that with the same condition on size of G we have actually (with few exceptions) a careful packing of G, that is an edge-disjoint placement of two copies of G into Kₙ∖Cₙ.
Ashwin Ganesan (2016)
Discussiones Mathematicae Graph Theory
Similarity:
Let S be a set of transpositions generating the symmetric group Sn (n ≥ 5). The transposition graph of S is defined to be the graph with vertex set {1, . . . , n}, and with vertices i and j being adjacent in T(S) whenever (i, j) ∈ S. In the present note, it is proved that two transposition graphs are isomorphic if and only if the corresponding two Cayley graphs are isomorphic. It is also proved that the transposition graph T(S) is edge-transitive if and only if the Cayley graph Cay(Sn,...
Chao, Chong-Yun (1967)
Portugaliae mathematica
Similarity:
Curtin, Eugen (2001)
Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]
Similarity:
Frank Harary, Edgar M. Palmer (1966)
Czechoslovak Mathematical Journal
Similarity:
Yi Wang, Yi-Zheng Fan, Xiao-Xin Li, Fei-Fei Zhang (2015)
Discussiones Mathematicae Graph Theory
Similarity:
A graph in a certain graph class is called minimizing if the least eigenvalue of its adjacency matrix attains the minimum among all graphs in that class. Bell et al. have identified a subclass within the connected graphs of order n and size m in which minimizing graphs belong (the complements of such graphs are either disconnected or contain a clique of size n/2 ). In this paper we discuss the minimizing graphs of a special class of graphs of order n whose complements are connected and...