Displaying similar documents to “Extremum degree sets of irregular oriented graphs and pseudodigraphs”

A characterization of complete tripartite degree-magic graphs

Ľudmila Bezegová, Jaroslav Ivančo (2012)

Discussiones Mathematicae Graph Theory

Similarity:

A graph is called degree-magic if it admits a labelling of the edges by integers 1, 2,..., |E(G)| such that the sum of the labels of the edges incident with any vertex v is equal to (1+ |E(G)|)/2*deg(v). Degree-magic graphs extend supermagic regular graphs. In this paper we characterize complete tripartite degree-magic graphs.

Degree sequences of digraphs with highly irregular property

Zofia Majcher, Jerzy Michael (1998)

Discussiones Mathematicae Graph Theory

Similarity:

A digraph such that for each its vertex, vertices of the out-neighbourhood have different in-degrees and vertices of the in-neighbourhood have different out-degrees, will be called an HI-digraph. In this paper, we give a characterization of sequences of pairs of out- and in-degrees of HI-digraphs.

3-Paths in Graphs with Bounded Average Degree

Stanislav Jendrol′, Mária Maceková, Mickaël Montassier, Roman Soták (2016)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper we study the existence of unavoidable paths on three vertices in sparse graphs. A path uvw on three vertices u, v, and w is of type (i, j, k) if the degree of u (respectively v, w) is at most i (respectively j, k). We prove that every graph with minimum degree at least 2 and average degree strictly less than m contains a path of one of the types [...] Moreover, no parameter of this description can be improved.

A Sokoban-type game and arc deletion within irregular digraphs of all sizes

Zyta Dziechcińska-Halamoda, Zofia Majcher, Jerzy Michael, Zdzisław Skupień (2007)

Discussiones Mathematicae Graph Theory

Similarity:

Digraphs in which ordered pairs of out- and in-degrees of vertices are mutually distinct are called irregular, see Gargano et al. [3]. Our investigations focus on the problem: what are possible sizes of irregular digraphs (oriented graphs) for a given order n? We show that those sizes in both cases make up integer intervals. The extremal sizes (the endpoints of these intervals) are found in [1,5]. In this paper we construct, with help of Sokoban-type game, n-vertex irregular oriented...

Characterization of 2 -minimally nonouterplanar join graphs

D. G. Akka, J. K. Bano (2001)

Mathematica Bohemica

Similarity:

In this paper, we present characterizations of pairs of graphs whose join graphs are 2-minimally nonouterplanar. In addition, we present a characterization of pairs of graphs whose join graphs are 2-minimally nonouterplanar in terms of forbidden subgraphs.