Search

In 1984, Bauer proposed the problems of determining best possible sufficient conditions on the vertex degrees of a simple graph (or a simple bipartite graph, or a simple triangle-free graph, respectively) G to ensure that its line graph L ( G ) is hamiltonian. We investigate the problems of determining best possible sufficient conditions on the vertex degrees of a simple graph G to ensure that its line graph L ( G ) is hamiltonian-connected, and prove the following. (i) For any real numbers a , b with 0 a 1 , there exists a finite family F ( a , b ) such that for any connected simple graph G on n vertices, if d G ( u ) + d G ( v ) ≥ a n + b for any u , v ∈ V ( G ) with u v ∉ E ( G ) , then either L ( G ) is hamiltonian-connected, or κ ( L ( G ) ) ≤ 2 , or L ( G ) is not hamiltonian-connected, κ ( L ( G ) ) ≥ 3 and G is contractible to a member in F ( a , b ) . (ii) Let G be a connected simple graph on n vertices. If d G ( u ) + d G ( v ) ≥ n 4 − 2 for any u , v ∈ V ( G ) with u v ∉ E ( G ) , then for sufficiently large n , either L ( G ) is hamiltonian-connected, or κ ( L ( G ) ) ≤ 2 , or L ( G ) is not hamiltonian-connected, κ ( L ( G ) ) ≥ 3 and G is contractible to W 8 , the Wagner graph. (iii) Let G be a connected simple triangle-free (or bipartite) graph on n vertices. If d G ( u ) + d G ( v ) ≥ n 8 for any u , v ∈ V ( G ) with u v ∉ E ( G ) , then for sufficiently large n , either L ( G ) is hamiltonian-connected, or κ ( L ( G ) ) ≤ 2 , or L ( G ) is not hamiltonian-connected, κ ( L ( G ) ) ≥ 3 and G is contractible to W 8 , the Wagner graph.

A very well-covered graph is an unmixed graph whose covering number is half of the number of vertices. We construct an explicit minimal free resolution of the cover ideal of a Cohen–Macaulay very well-covered graph. Using this resolution, we characterize the projective dimension of the edge ideal of a very well-covered graph in terms of a pairwise$3$-disjoint set of complete bipartite subgraphs of the graph. We also show nondecreasing property of the projective dimension of symbolic powers of the edge ideal of a very well-covered graph with respect to the exponents.

Studying the space-like graph surfaces of codimension 2 on the five-dimensional sub-Lorentzian structures with two negative directions of distinct degrees, we determine the differential properties of graph mappings and prove the area formula for the corresponding image surfaces.

A structural characterization of graphs not containing the Wagner graph, also known as V 8 , is shown. The result was announced in 1979 by the second author, but until now a proof has not been published.

Building on recent work of Dvořak and Yepremyan, we show that every simple graph of minimum degree 7 t + 7 contains K t as an immersion and that every graph with chromatic number at least 3.54 t + 4 contains K t as an immersion.

Given a graph G and a finite set T of non-negative integers containing zero, a T-coloring of G is a non-negative integer function f defined on V(G) such that $$|f(x)-f(y)|\not \in T$$ whenever $$(x,y)\in E(G)$$ . The span of T-coloring is the difference between the largest and smallest colors, and the T-span of G is the minimum span over all T-colorings f of G. The edge span of a T-coloring is the maximum value of $$|f(x)-f(y)|$$ over all edges $$(x,y)\in E(G)$$ , and the T-edge span of G is the minimum edge span over all T-colorings f of G. In this paper, we compute T-span and T-edge span of crown graph, circular ladder and mobius ladder, generalized theta graph, series-parallel graph and wrapped butterfly network.

Let G be a graph embedded in a nonspherical orientable surface with face-width ≥ 19. We prove that G contains a minor isomorphic to K 7 .

Sub-Lorentzian analogues of the area formula for graph mappings on four-dimensional subLorentzian structures are proved.

The number of spanning trees of a graph G is the total number of distinct spanning subgraphs of G that are trees. In this paper, we present sharp upper bounds for the number of spanning trees of a graph with given matching number.

Using Lotker's interlacing theorem on the Laplacian eigenvalues of a graph in [3] and Wang and Belardo's interlacing theorem on the signless Laplacian eigenvalues of a graph in [4], we obtain inequalities which involve the independence number, chromatic number, Laplacian eigenvalues, and signless Laplacian eigenvalues of a graph. Moreover, using a theorem proved by Hoffman in [2] and a theorem proved by Wilf in [5], we obtain upper bounds for the total chromatic number of a graph.

An independent set of a graph is a set of pairwise non-adjacent vertices while the independence number is the maximum cardinality of an independent set in the graph. The independence polynomial of a graph is defined as a polynomial in which the coefficient is the number of the independent set in the graph. Meanwhile, a graph of a group G is called n-th central if the vertices are elements of G and two distinct vertices are adjacent if they are elements in the n-th term of the upper central series of G. In this research, the independence polynomial of the n-th central graph is found for some dihedral groups.

A graph is a mathematical structure which consists of vertices and edges that is used to model relations between object. In this research, the generalized conjugacy class graph is constructed for some dihedral groups to show the relation between orbits and their cardinalities. In order to construct the graph, the probability that an element of the dihedral groups fixes a set must first be obtained. The set under this study is the set of all pairs of commuting elements in the form of (a,b) where a and b are elements of the dihedral groups and the lowest common multiple of the order of the elements is two. The orbits of the set are then computed using conjugation action. Based on the results obtained, the generalized conjugacy class graph is constructed and some graph properties are also found.

Let G be a dihedral group and Gamma its conjugacy class graph. The Laplacian energy of the graph, LE(Gamma) is defined as the sum of the absolute values of the difference between the Laplacian eigenvalues and the ratio of twice the edges number divided by the number of vertices. In this research, the Laplacian matrices of the conjugacy class graph of some dihedral groups and its eigenvalues are first computed. Then, the Laplacian energy of this graph is determined.

In this chapter we study how global parameters of a graph, such as its edge density or chromatic number, can influence its local substructures. How many edges, for instance, do we have to give a graph on n vertices to be sure that, no matter how these edges are arranged, the graph will contain a K r subgraph for some given r? Or at least a K r minor? Will some sufficiently high average degree or chromatic number ensure that one of these substructures occurs?

The lower bound for the chromatic number of $$\mathbb {R}^4$$R4 is improved from $$7$$7 to $$9$$9. Three graphs with unit distance embeddings in $$\mathbb {R}^4$$R4 are described. The first is a $$7$$7-chromatic graph of order $$14$$14 whose chromatic number can be verified by inspection. The second is an $$8$$8-chromatic graph of order $$26$$26. In this case the chromatic number can be verified quickly by a simple computer program. The third graph is a $$9$$9-chromatic graph of order $$65$$65 for which computer verification takes about one minute.

A ranking on a graph is an assignment of positive integers to its vertices such that any path between two vertices with the same label contains a vertex with a larger label. The rank number of a graph is the fewest number of labels that can be used in a ranking. The rank number of a graph is known for many families, including the ladder graph P2 × Pn. We consider how ”bending” a ladder affects the rank number. We prove that in certain cases the rank number does not change, and in others the rank number differs by only 1. We investigate the rank number of a ladder with an arbitrary number of bends.

Gutman and Wagner I. Gutman, S. Wagner, The matching energy of a graph, Discrete Appl. Math. 160 (2012) 2177-2187] defined the matching energy of a graph and gave some properties and asymptotic results of the matching energy. In this paper, we characterize the connected graph G with the connectivity ? (resp. chromatic number ? ) which has the maximum matching energy.

In this paper, the conjugacy classes of three metabelian groups, namely the Quasi-dihedral group, Dihedral group and Quaternion group of order 16 are computed. The obtained results are then applied to graph theory, more precisely to conjugate graph and conjugacy class graph. Some graph properties such as chromatic number, clique number, dominating number and independent number are found.

Let Ks,t* denote the graph obtained from the complete graph Ks+t by deleting the edges of some Kt-subgraph. The author proved earlier that for each fixed s and t>t0s:=max{415s2+s,240slog2s8slog2s+1}, every graph with chromatic number s+t has a Ks,t* minor. This confirmed a partial case of the corresponding conjecture by Woodall and Seymour. In this paper, we show that the statement holds already for much smaller t, namely, for t>Cslogs3.

Let be a commutative ring. The prime graph of the ring is defined as a graph whose vertex set consists of all elements of and any two distinct vertices x and y are adjacent if and only if or . This graph is denoted by . In this paper we investigate some relations between the chromatic number of prime graph of finite product of commutative rings and the chromatic number of prime graph of these rings. We also obtain some results on the chromatic number of prime graph of the ring .

We introduce the notion of the semi-chromatic number of a graph with a nonempty number of edges. Then we prove that the difference between the semi-chromatic number and the half of the chromatic number is at most 1.

In the algorithm for the disjoint paths problem given in Graph Minors XIII, we used without proof a lemma that, in solving such a problem, a vertex which was sufficiently “insulated” from the rest of the graph by a large planar piece of the graph was irrelevant, and could be deleted without changing the problem. In this paper we prove the lemma.

Let A = D A + B be a block r × r, r ≥ 2, Hermitian matrix of order n, where D A is the block diagonal part of A. The main results of the paper are Theorems 2.1 and 2.2, which state the sharp inequalities $$ {\lambda_1}(A) \geqslant {\lambda_1}\left( {{D_A} + \xi B} \right)\,\,\,and\,\,\,{\lambda_n}(A) \leqslant {\lambda_n}\left( {{D_A} + \xi B} \right), - \frac{1}{{r - 1}} \leqslant \xi \leqslant 1, $$ and analyze the equality cases. Some implications of these results are indicated. As applications, matrices occurring in spectral graph theory are considered, and new lower bounds on the chromatic number of a graph are obtained. Bibliography: 7 titles.

We prove that the chromatic Ramsey number of every odd wheel W2k+ 1, k⩾2 is 14. That is, for every odd wheel W2k+ 1, there exists a 14-chromatic graph F such that when the edges of F are two-coloured, there is a monochromatic copy of W2k+ 1 in F, and no graph F with chromatic number 13 has the same property. We ask whether a natural extension of odd wheels to the family of generalized Mycielski graphs could help to prove the Burr–Erdős–Lovasz conjecture on the minimum possible chromatic Ramsey number of an n-chromatic graph. © 2011 Wiley Periodicals, Inc. J Graph Theory 69:198-205, 2012

Let [Formula: see text] be a commutative ring with nonzero identity and [Formula: see text] be the Jacobson radical of [Formula: see text]. The Jacobson graph of [Formula: see text], denoted by [Formula: see text], is a graph with vertex-set [Formula: see text], such that two distinct vertices [Formula: see text] and [Formula: see text] in [Formula: see text] are adjacent if and only if [Formula: see text] is not a unit of [Formula: see text]. The goal in this paper is to list every finite commutative ring [Formula: see text] with nonzero identity (up to isomorphism) such that the graph [Formula: see text] is projective.

We present two new proofs of the q-commuting property holding among certain pairs of quantum minors of a q-generic matrix. The first uses elementary quasi-determinantal arithmetic; the second involves paths in a directed graph. Together, they indicate a means to build the multi-homogeneous coordinate rings of flag varieties in other non-commutative settings.

Let S be a set of n ⩾ 4 points in general position in the plane, and let h n be the number of extreme points of S. We show how to construct a 3-connected plane graph with vertex set S, having max { ⌈ 3 n / 2 ⌉ , n + h − 1 } edges, and we prove that there is no 3-connected plane graph on top of S with a smaller number of edges. In particular, this implies that S admits a 3-connected cubic plane graph if and only if n ⩾ 4 is even and h ⩽ n / 2 + 1 . The same bounds also hold when 3-edge-connectivity is considered. We also give a partial characterization of the point sets in the plane that can be the vertex set of a cubic plane graph.

In this paper, we present a very simple polynomial and greedy algorithm, with a computer program, for finding an approximate value of the chromatic number (an upper bound) γ(G) of a given finite and simple graph G.

We provide a characterization of several graph parameters (the acyclic chromatic number, the arrangeability, and a sequence of parameters related to the expansion of a graph) in terms of forbidden subdivisions.

This note presents two new upper bounds for the number of spanning trees of a graph in terms of the order, edge number and maximum degree of a graph.

We prove a conjecture stating that the branchwidth of a graph and the branchwidth of the graph's cycle matroid are equal if the graph has a cycle of length at least 2.

We give a new upper bound for the rectilinear crossing number [email protected]?(n) of the complete geometric graph K"n. We prove that [email protected]?(n)=

In the core of the seminal Graph Minor Theory of Robertson and Seymour lies a powerful theorem capturing the ``rough'' structure of graphs excluding a fixed minor. This result was used to prove Wagner's Conjecture that finite graphs are well-quasi-ordered under the graph minor relation. Recently, a number of beautiful results that use this structural result have appeared. Some of these along with some other recent advances on graph minors are surveyed.