The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
A graph Γ has the property C(m,n) if, whenever M, N are disjoint sets of vertices of Γ with |M|=m and |N|=n, there exists a cycle in Γ which includes all the vertices of M and which avoids all the vertices of N. Let G be a group generated by a subset X of G. We denote by G(X) the graph whose vertices are elements of G and two vertices a, b are adjacent if and only if a−1 e X U X−1. The graph G(X)...
The notion of degree sequence (sometimes called valence sequence) of a graph is the basic theme in this discussion. Degree sequences are first considered in the context of simple graphs. Subsequently they are generalized to a wider setting which unifies various standard extensions of the definition of graph, and introduces further types of graph in a natural way.
We survey the results obtained by a large number of authors concerning the spectrum of a graph. The questions of characterisation by spectrum, cospectral graphs and information derived from the spectrum are discussed.
Under certain circumstances it is possible to fit rectangles of size m × n into a larger rectangle of size p × q so that they fit exactly. When this is not the case the minimum wastage should be determined. A number of results are in the literature. We discuss the case where m=2. The terms n, p, q are, of course, natural numbers.
Some problems concerning the stability index of the permutation graph (Pn, π) are investigated. It is shown that for a certain class of permutation graphs, called Roman numerals, the stability index can be only 2n, 2n − 4, 2n − 5, 2n − 6 or 2n − 7. The general situation for (Pn, π) is more complicated and some open questions are listed.
We prove Grant's conjecture that, for all graphs G and H with H ≇ K1, the lexicographic product G[H] is semi-stable at (v, w) if H is semi-stable at w. Thus we can conclude that G[H] is semi-stable at (v, w) if and only if H is semi-stable at w.
Let M, N be any disjoint subsets of the vertex set of the graph G with ‖M‖=m and ‖N‖=n. We say that G ε C(m, n) if there is a cycle K in G such that M $$\subseteq$$ VK and N∩VK=φ. If g Is k-connected, then it is an old result of Dirac that G ε C(k, 0). It is easy to produce k-connected graphs which are not C(k+1, 0). Hence the best we can hope of an arbitrary k-connected graph is that it is...
If G and H are two connected non-trivial graphs, not necessarily of finite order, then we show that the cartesian product G × H, is stable in the sense of Sheehan [4]. Moreover except when G=P2 and H is a certain restricted class of prime graphs, any edge of G × H may be removed to give the stability, i.e. G × H is completely stable. Consideration is given to the case where G × H is not connected...
This paper investigates some of the fundamental relationships between various nonisomorphic pseudographs (generalized graphs in which loops and multiple edges are permitted) which have the same degree sequence.
This paper investigates pseudographs with degree sequences which have infinitely many terms greater than 1. Two nonisomorphic pseudographs with the same degree sequence are adjacent if one can be obtained from the other by an elementary operation called switching. With this notion of adjacency we can regard distinct pseudographs with the same degree sequence as the vertices of a graph, called the...
Abstract.We establish that if A is a set of at most 23 vertices in a 3-connected cubic planar graph G, then there is a cycle in G containing A. This result is sharp.
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.